ReslandDSA Study Center

Recursion

Solve a problem by calling the same function on a smaller piece of it, until the piece is small enough to answer directly.

BeginnerRead first: Big-O & Complexity

How It Works

A recursive function solves a problem by handing a smaller copy of the same problem to itself. It always has two parts: a base case that's small enough to answer directly, and a recursive case that shrinks the input, calls itself and builds its answer from the result. As long as every call moves closer to the base case, the recursion ends.

Each call waits on the call stack until the call it made returns. Here's factorial(4) working down to the base case, then the answers flowing back up:

factorial(4)
  = 4 * factorial(3)                  calls go down
        = 3 * factorial(2)
              = 2 * factorial(1)
                    = 1               base case
              = 2 * 1 = 2             answers come back up
        = 3 * 2 = 6
  = 4 * 6 = 24
At the deepest point four calls are on the stack at once. That's why recursion n levels deep costs O(n) space.

The Call Stack of factorial(4)

Step 1 of 8

calls made

call stack

  • Running now
  • Waiting for its call to return
  • Returned

Call factorial(4). 4 isn't <= 1, so it can't answer directly. It calls factorial(3) and waits on the stack for the result.

All 8 steps as text
  1. Call factorial(4). 4 isn't <= 1, so it can't answer directly. It calls factorial(3) and waits on the stack for the result.
  2. factorial(3) goes on top of the stack. It needs factorial(2) first, so it calls it and waits too. Trust that call to return 2!.
  3. factorial(2) does the same: it calls factorial(1) and waits. The stack is 3 calls deep now.
  4. factorial(1) is the base case: 1 <= 1, so it returns 1 without another call. This is the deepest point, with 4 calls on the stack at once.
  5. factorial(1) returns 1 and leaves the stack. factorial(2) picks up where it stopped and computes 2 * 1 = 2.
  6. factorial(2) returns 2 and leaves the stack. factorial(3) picks up where it stopped and computes 3 * 2 = 6.
  7. factorial(3) returns 6 and leaves the stack. factorial(4) picks up where it stopped and computes 4 * 6 = 24.
  8. factorial(4) returns 24 and the stack is empty again. 4 calls did O(1) work each, and at the deepest point all 4 were on the stack: O(n) time and O(n) space.

Two habits make recursive code easy to write. First, trust the recursive call: assume factorial(n - 1) returns the right answer and only work out how to build factorial(n) from it. Second, write the base case first and check that every recursive call moves toward it. Most recursive code takes one of three shapes:

  • One call on a slightly smaller input. Factorial, summing a list, walking a linked list. The stack grows as deep as the input is long.
  • One call on half the input. Fast exponentiation and binary search. Only O(log n) levels deep.
  • Several calls per level. Flood fill, tree traversals and backtracking. The total work is the size of the whole call tree. That's linear when each node or cell is handled once, as in flood fill. It's exponential when the tree branches at every level: backtracking does that on purpose to try every combination, and naive Fibonacci does it by accident, because its branches repeat each other. Caching those repeats is how dynamic programming starts.

When to Reach for It

  • The input is defined in terms of itself: a tree, a nested list, or a region of connected cells in a grid.
  • You can state the answer for n easily if someone hands you the answer for n - 1 or n / 2.
  • You have to explore every path, choice or combination, and each step has only a few options.
  • The work spreads outward from a starting point, like paint filling a region.

Complexity

OperationTimeSpace
One call per step down (factorial, linked list)O(n)O(n) call stack
Halve the input on each call (fast power)O(log n)O(log n) call stack
Visit each node or cell once (flood fill, tree traversal)O(n)O(depth), up to O(n)
Two calls per level with no caching (naive Fibonacci)O(2^n)O(n) call stack

The Template

Base Case and Recursive Case

factorial(n) multiplies n by every positive integer below it. The base case answers n <= 1 directly with 1, which also covers 0! = 1. The recursive case trusts factorial(n - 1) and multiplies the result by n. Each call lowers n by one, so every non-negative input reaches the base case.

There are n calls doing O(1) work each, so the time is O(n). The space is O(n) too, because every one of those calls waits on the stack until the base case returns. A loop would compute the same product in O(1) space, so recursion isn't the best tool for this particular job. It earns its keep when the problem branches, as trees and grids do, where a loop would need a stack of its own.

Time O(n)Space O(n) call stack

def factorial(n: int) -> int:
    """n! = n * (n - 1) * ... * 1, with 0! = 1."""
    if n <= 1:
        return 1  # Base case: small enough to answer directly.
    return n * factorial(n - 1)  # Recursive case: trust the smaller call, then do one step.


if __name__ == "__main__":
    print(factorial(0))  # 1
    print(factorial(4))  # 24
    print(factorial(10))  # 3628800
// n! = n * (n - 1) * ... * 1, with 0! = 1.
export function factorial(n: number): number {
  if (n <= 1) return 1; // Base case: small enough to answer directly.
  return n * factorial(n - 1); // Recursive case: trust the smaller call, then do one step.
}

console.log(factorial(0)); // 1
console.log(factorial(4)); // 24
console.log(factorial(10)); // 3628800
package main

import "fmt"

// factorial returns n! = n * (n - 1) * ... * 1, with 0! = 1.
func factorial(n int) int {
	if n <= 1 {
		return 1 // Base case: small enough to answer directly.
	}
	return n * factorial(n-1) // Recursive case: trust the smaller call, then do one step.
}

func main() {
	fmt.Println(factorial(0))  // 1
	fmt.Println(factorial(4))  // 24
	fmt.Println(factorial(10)) // 3628800
}
using System;

public class Solution
{
    // n! = n * (n - 1) * ... * 1, with 0! = 1.
    public static long Factorial(int n)
    {
        if (n <= 1) return 1; // Base case: small enough to answer directly.
        return n * Factorial(n - 1); // Recursive case: trust the smaller call, then do one step.
    }

    public static void Main()
    {
        Console.WriteLine(Factorial(0)); // 1
        Console.WriteLine(Factorial(4)); // 24
        Console.WriteLine(Factorial(10)); // 3628800
    }
}
public class Solution {
    // n! = n * (n - 1) * ... * 1, with 0! = 1.
    static long factorial(int n) {
        if (n <= 1) return 1; // Base case: small enough to answer directly.
        return n * factorial(n - 1); // Recursive case: trust the smaller call, then do one step.
    }

    public static void main(String[] args) {
        System.out.println(factorial(0)); // 1
        System.out.println(factorial(4)); // 24
        System.out.println(factorial(10)); // 3628800
    }
}

Worked Problems

Each solution stays folded until you open it, so you can try the problem first. Every one is a complete program in Python, TypeScript, Go, C# and Java, run and checked against its expected output.

Pow(x, n)

MEDIUMLeetCode 50

Problem

Write a function that raises a floating-point number x to an integer power n, without the language's built-in power function. The exponent can be negative, and it can be anywhere in the 32-bit range, so multiplying x by itself n times is far too slow. You can assume x isn't 0 when n is negative, and that the answer stays between -10^4 and 10^4.

Example: x = 2.0, n = 10 gives 1024.00000. x = 2.0, n = -2 gives 0.25000, because a negative exponent means one over the positive power: 1 / 4.

Show Solution

Approach

Fast exponentiation halves the exponent on every call. Let half be x to the power n / 2, with the division rounded down. When n is even the answer is half * half. When n is odd, rounding down lost one factor of x, so the answer is half * half * x. The base case is n == 0, which returns 1.

power(2, 10) = 32 * 32     = 1024
power(2, 5)  = 4 * 4 * 2   = 32
power(2, 2)  = 2 * 2       = 4
power(2, 1)  = 1 * 1 * 2   = 2
power(2, 0)  base case     = 1
Read from the bottom up. Each line squares the answer from the line below, and odd exponents multiply in one more 2.

Each call does O(1) work and halves n, so an exponent near two billion takes only about 32 calls. Compute half once and use it twice. Writing power(x, n / 2) * power(x, n / 2) makes two calls per level, the doubling cancels out the halving, and you're back to O(n) calls.

Negative exponents are handled once, up front: compute the positive power and take its reciprocal. In C# and Java, negating -2147483648 overflows back to itself, so those versions copy n into a 64-bit long first. The last demo line is exactly that case.

Time O(log n)Space O(log n) call stack

def my_pow(x: float, n: int) -> float:
    """x raised to the power n, for any integer n, by fast exponentiation."""
    # A negative power is the reciprocal of the positive one.
    if n < 0:
        return 1 / power(x, -n)
    return power(x, n)


def power(x: float, n: int) -> float:
    """x to the power n for n >= 0, halving n on every call."""
    if n == 0:
        return 1.0  # Base case: anything to the power 0 is 1.
    half = power(x, n // 2)  # One call, used twice.
    return half * half if n % 2 == 0 else half * half * x


if __name__ == "__main__":
    print(f"{my_pow(2.0, 10):.5f}")  # 1024.00000
    print(f"{my_pow(2.1, 3):.5f}")  # 9.26100
    print(f"{my_pow(2.0, -2):.5f}")  # 0.25000
    print(f"{my_pow(-1.0, -2147483648):.5f}")  # 1.00000
// x raised to the power n, for any integer n, by fast exponentiation.
export function myPow(x: number, n: number): number {
  // A negative power is the reciprocal of the positive one.
  if (n < 0) return 1 / power(x, -n);
  return power(x, n);
}

// x to the power n for n >= 0, halving n on every call.
function power(x: number, n: number): number {
  if (n === 0) return 1; // Base case: anything to the power 0 is 1.
  const half = power(x, Math.floor(n / 2)); // One call, used twice.
  return n % 2 === 0 ? half * half : half * half * x;
}

console.log(myPow(2.0, 10).toFixed(5)); // 1024.00000
console.log(myPow(2.1, 3).toFixed(5)); // 9.26100
console.log(myPow(2.0, -2).toFixed(5)); // 0.25000
console.log(myPow(-1.0, -2147483648).toFixed(5)); // 1.00000
package main

import "fmt"

// myPow returns x raised to the power n, for any integer n, by fast
// exponentiation.
func myPow(x float64, n int) float64 {
	// A negative power is the reciprocal of the positive one.
	if n < 0 {
		return 1 / power(x, -n)
	}
	return power(x, n)
}

// power returns x to the power n for n >= 0, halving n on every call.
func power(x float64, n int) float64 {
	if n == 0 {
		return 1 // Base case: anything to the power 0 is 1.
	}
	half := power(x, n/2) // One call, used twice.
	if n%2 == 0 {
		return half * half
	}
	return half * half * x
}

func main() {
	fmt.Printf("%.5f\n", myPow(2.0, 10))           // 1024.00000
	fmt.Printf("%.5f\n", myPow(2.1, 3))            // 9.26100
	fmt.Printf("%.5f\n", myPow(2.0, -2))           // 0.25000
	fmt.Printf("%.5f\n", myPow(-1.0, -2147483648)) // 1.00000
}
using System;
using System.Globalization;

public class Solution
{
    // x raised to the power n, for any int n, by fast exponentiation.
    public static double MyPow(double x, int n)
    {
        // Widen first: -n overflows when n is int.MinValue.
        long exponent = n;
        // A negative power is the reciprocal of the positive one.
        if (exponent < 0) return 1 / Power(x, -exponent);
        return Power(x, exponent);
    }

    // x to the power n for n >= 0, halving n on every call.
    static double Power(double x, long n)
    {
        if (n == 0) return 1; // Base case: anything to the power 0 is 1.
        double half = Power(x, n / 2); // One call, used twice.
        return n % 2 == 0 ? half * half : half * half * x;
    }

    public static void Main()
    {
        Console.WriteLine(MyPow(2.0, 10).ToString("F5", CultureInfo.InvariantCulture)); // 1024.00000
        Console.WriteLine(MyPow(2.1, 3).ToString("F5", CultureInfo.InvariantCulture)); // 9.26100
        Console.WriteLine(MyPow(2.0, -2).ToString("F5", CultureInfo.InvariantCulture)); // 0.25000
        Console.WriteLine(MyPow(-1.0, -2147483648).ToString("F5", CultureInfo.InvariantCulture)); // 1.00000
    }
}
import java.util.Locale;

public class Solution {
    // x raised to the power n, for any int n, by fast exponentiation.
    static double myPow(double x, int n) {
        // Widen first: -n overflows when n is Integer.MIN_VALUE.
        long exponent = n;
        // A negative power is the reciprocal of the positive one.
        if (exponent < 0) return 1 / power(x, -exponent);
        return power(x, exponent);
    }

    // x to the power n for n >= 0, halving n on every call.
    static double power(double x, long n) {
        if (n == 0) return 1; // Base case: anything to the power 0 is 1.
        double half = power(x, n / 2); // One call, used twice.
        return n % 2 == 0 ? half * half : half * half * x;
    }

    public static void main(String[] args) {
        // Locale.ROOT keeps the decimal point a "." on every machine.
        System.out.println(String.format(Locale.ROOT, "%.5f", myPow(2.0, 10))); // 1024.00000
        System.out.println(String.format(Locale.ROOT, "%.5f", myPow(2.1, 3))); // 9.26100
        System.out.println(String.format(Locale.ROOT, "%.5f", myPow(2.0, -2))); // 0.25000
        System.out.println(String.format(Locale.ROOT, "%.5f", myPow(-1.0, -2147483648))); // 1.00000
    }
}

Flood Fill

EASYLeetCode 733

Problem

An image is a grid of integers, one color per pixel. Starting at pixel (sr, sc), repaint it with a new color, along with every pixel connected to it through up, down, left or right steps that had the same original color. Return the repainted image.

Example: filling [[1, 1, 1], [1, 1, 0], [1, 0, 1]] from (1, 1) with color 2 gives [[2, 2, 2], [2, 2, 0], [2, 0, 1]]. The 1 in the bottom-right corner only touches the region diagonally, so it keeps its color.

Show Solution

Approach

Write a helper, fill, that paints the pixel at (r, c) and then calls itself on the four neighbors. The base case returns straight away when the pixel is off the grid or isn't the original color. That one check stops the recursion at the region's edges, and it also stops it at pixels that are already painted, because their color has changed.

If the new color equals the original, return the image before you start. Otherwise a freshly painted pixel still looks like part of the region, and the calls bounce between neighbors until the stack overflows.

Flood Fill, Call by Call

Step 1 of 14

image

call stack

  • Call running now
  • Call waiting on the stack
  • Painted, call returned
  • Wrong color, call returns at once

Fill from (1, 1) with 2. The region is every 1 you can reach from there by stepping up, down, left or right.

All 14 steps as text
  1. Fill from (1, 1) with 2. The region is every 1 you can reach from there by stepping up, down, left or right.
  2. Call fill(1, 1). It's the original color 1, so paint it 2, then call fill on its neighbors: down, up, right and left.
  3. (2, 1) isn't a 1, so that call returns at once. fill(1, 1) calls fill(0, 1), one step up. It's a 1, so paint it 2 and go one frame deeper.
  4. (-1, 1) is off the grid and (1, 1) is painted already, so those calls return at once. fill(0, 1) calls fill(0, 2), one step right. It's a 1, so paint it 2 and go one frame deeper.
  5. (-1, 2) and (0, 3) are off the grid, (0, 1) is painted already, and (1, 2) isn't a 1. All four neighbor calls of fill(0, 2) are done, so it returns to fill(0, 1).
  6. fill(0, 1) calls fill(0, 0), one step left. It's a 1, so paint it 2 and go one frame deeper.
  7. fill(0, 0) calls fill(1, 0), one step down. It's a 1, so paint it 2 and go one frame deeper.
  8. fill(1, 0) calls fill(2, 0), one step down. It's a 1, so paint it 2 and go one frame deeper.
  9. (3, 0) and (2, -1) are off the grid, (1, 0) is painted already, and (2, 1) isn't a 1. All four neighbor calls of fill(2, 0) are done, so it returns to fill(1, 0).
  10. (1, -1) is off the grid, and (0, 0) and (1, 1) are painted already. All four neighbor calls of fill(1, 0) are done, so it returns to fill(0, 0).
  11. (-1, 0) and (0, -1) are off the grid, and (0, 1) is painted already. All four neighbor calls of fill(0, 0) are done, so it returns to fill(0, 1).
  12. All four neighbor calls of fill(0, 1) are done, so it returns to fill(1, 1).
  13. (1, 0) is painted already and (1, 2) isn't a 1. fill(1, 1) has tried all four neighbors and returns. The fill is complete.
  14. 6 pixels painted, each exactly once, so the time is O(m · n). The stack peaked at 5 calls. The bottom-right 1 only touches the region diagonally, so no call reached it.

Time O(m · n)Space O(m · n) call stack in the worst case

import sys

# A 50 x 50 region recurses up to 2,500 calls deep, past Python's default
# limit of 1,000 frames.
sys.setrecursionlimit(10_000)


def flood_fill(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
    """Repaints the pixel at (sr, sc) and every pixel connected to it, up, down,
    left or right, that has the same original color."""
    original = image[sr][sc]
    # Painting a color over itself changes nothing, and the recursion would
    # never see a pixel as done.
    if original == color:
        return image
    fill(image, sr, sc, original, color)
    return image


def fill(image: list[list[int]], r: int, c: int, original: int, color: int) -> None:
    """Paints (r, c) if it's in the region, then spreads to its four neighbors."""
    # Base case: off the grid, or not part of the region (or painted already).
    if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]):
        return
    if image[r][c] != original:
        return
    image[r][c] = color
    fill(image, r + 1, c, original, color)
    fill(image, r - 1, c, original, color)
    fill(image, r, c + 1, original, color)
    fill(image, r, c - 1, original, color)


if __name__ == "__main__":
    print(flood_fill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2))  # [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
    print(flood_fill([[0, 0, 0], [0, 0, 0]], 0, 0, 0))  # [[0, 0, 0], [0, 0, 0]]
    print(flood_fill([[0, 0, 0], [0, 1, 0], [0, 0, 0]], 0, 0, 3))  # [[3, 3, 3], [3, 1, 3], [3, 3, 3]]
// Repaints the pixel at (sr, sc) and every pixel connected to it, up, down,
// left or right, that has the same original color.
export function floodFill(image: number[][], sr: number, sc: number, color: number): number[][] {
  const original = image[sr][sc];
  // Painting a color over itself changes nothing, and the recursion would
  // never see a pixel as done.
  if (original === color) return image;
  fill(image, sr, sc, original, color);
  return image;
}

// Paints (r, c) if it's in the region, then spreads to its four neighbors.
function fill(image: number[][], r: number, c: number, original: number, color: number): void {
  // Base case: off the grid, or not part of the region (or painted already).
  if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
  if (image[r][c] !== original) return;
  image[r][c] = color;
  fill(image, r + 1, c, original, color);
  fill(image, r - 1, c, original, color);
  fill(image, r, c + 1, original, color);
  fill(image, r, c - 1, original, color);
}

console.log(JSON.stringify(floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2))); // [[2,2,2],[2,2,0],[2,0,1]]
console.log(JSON.stringify(floodFill([[0, 0, 0], [0, 0, 0]], 0, 0, 0))); // [[0,0,0],[0,0,0]]
console.log(JSON.stringify(floodFill([[0, 0, 0], [0, 1, 0], [0, 0, 0]], 0, 0, 3))); // [[3,3,3],[3,1,3],[3,3,3]]
package main

import "fmt"

// floodFill repaints the pixel at (sr, sc) and every pixel connected to it,
// up, down, left or right, that has the same original color.
func floodFill(image [][]int, sr, sc, color int) [][]int {
	original := image[sr][sc]
	// Painting a color over itself changes nothing, and the recursion would
	// never see a pixel as done.
	if original == color {
		return image
	}
	fill(image, sr, sc, original, color)
	return image
}

// fill paints (r, c) if it's in the region, then spreads to its four neighbors.
func fill(image [][]int, r, c, original, color int) {
	// Base case: off the grid, or not part of the region (or painted already).
	if r < 0 || r >= len(image) || c < 0 || c >= len(image[0]) {
		return
	}
	if image[r][c] != original {
		return
	}
	image[r][c] = color
	fill(image, r+1, c, original, color)
	fill(image, r-1, c, original, color)
	fill(image, r, c+1, original, color)
	fill(image, r, c-1, original, color)
}

func main() {
	fmt.Println(floodFill([][]int{{1, 1, 1}, {1, 1, 0}, {1, 0, 1}}, 1, 1, 2)) // [[2 2 2] [2 2 0] [2 0 1]]
	fmt.Println(floodFill([][]int{{0, 0, 0}, {0, 0, 0}}, 0, 0, 0))            // [[0 0 0] [0 0 0]]
	fmt.Println(floodFill([][]int{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 0, 3)) // [[3 3 3] [3 1 3] [3 3 3]]
}
using System;
using System.Linq;

public class Solution
{
    // Repaints the pixel at (sr, sc) and every pixel connected to it, up, down,
    // left or right, that has the same original color.
    public static int[][] FloodFill(int[][] image, int sr, int sc, int color)
    {
        int original = image[sr][sc];
        // Painting a color over itself changes nothing, and the recursion would
        // never see a pixel as done.
        if (original == color) return image;
        Fill(image, sr, sc, original, color);
        return image;
    }

    // Paints (r, c) if it's in the region, then spreads to its four neighbors.
    static void Fill(int[][] image, int r, int c, int original, int color)
    {
        // Base case: off the grid, or not part of the region (or painted already).
        if (r < 0 || r >= image.Length || c < 0 || c >= image[0].Length) return;
        if (image[r][c] != original) return;
        image[r][c] = color;
        Fill(image, r + 1, c, original, color);
        Fill(image, r - 1, c, original, color);
        Fill(image, r, c + 1, original, color);
        Fill(image, r, c - 1, original, color);
    }

    public static void Main()
    {
        Console.WriteLine(Format(FloodFill(new[] { new[] { 1, 1, 1 }, new[] { 1, 1, 0 }, new[] { 1, 0, 1 } }, 1, 1, 2))); // [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
        Console.WriteLine(Format(FloodFill(new[] { new[] { 0, 0, 0 }, new[] { 0, 0, 0 } }, 0, 0, 0))); // [[0, 0, 0], [0, 0, 0]]
        Console.WriteLine(Format(FloodFill(new[] { new[] { 0, 0, 0 }, new[] { 0, 1, 0 }, new[] { 0, 0, 0 } }, 0, 0, 3))); // [[3, 3, 3], [3, 1, 3], [3, 3, 3]]
    }

    static string Format(int[][] grid) =>
        "[" + string.Join(", ", grid.Select(row => "[" + string.Join(", ", row) + "]")) + "]";
}
import java.util.Arrays;

public class Solution {
    // Repaints the pixel at (sr, sc) and every pixel connected to it, up, down,
    // left or right, that has the same original color.
    static int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int original = image[sr][sc];
        // Painting a color over itself changes nothing, and the recursion would
        // never see a pixel as done.
        if (original == color) return image;
        fill(image, sr, sc, original, color);
        return image;
    }

    // Paints (r, c) if it's in the region, then spreads to its four neighbors.
    static void fill(int[][] image, int r, int c, int original, int color) {
        // Base case: off the grid, or not part of the region (or painted already).
        if (r < 0 || r >= image.length || c < 0 || c >= image[0].length) return;
        if (image[r][c] != original) return;
        image[r][c] = color;
        fill(image, r + 1, c, original, color);
        fill(image, r - 1, c, original, color);
        fill(image, r, c + 1, original, color);
        fill(image, r, c - 1, original, color);
    }

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(floodFill(new int[][] {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}}, 1, 1, 2))); // [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
        System.out.println(Arrays.deepToString(floodFill(new int[][] {{0, 0, 0}, {0, 0, 0}}, 0, 0, 0))); // [[0, 0, 0], [0, 0, 0]]
        System.out.println(Arrays.deepToString(floodFill(new int[][] {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0, 0, 3))); // [[3, 3, 3], [3, 1, 3], [3, 3, 3]]
    }
}

Common Pitfalls

  • A base case the recursion can step over. If n drops by 2 each call and the base case only checks n == 1, an even n skips right past it and never stops. Prefer n <= 1 to n == 1.
  • Solving the same subproblem again and again. Naive Fibonacci reaches fib(n - 2) from two different calls, and the repeats make it exponential. Cache results when calls overlap, which is the first step toward dynamic programming.
  • Leaving the call stack out of the space cost. A recursion n calls deep uses O(n) memory even if it never allocates anything.
  • Copying the input on every call. Passing nums[1:] or a substring copies O(n) elements each time and turns an O(n) recursion into O(n²). Pass an index instead.
  • Recursing as deep as the input is long. Python stops at 1,000 frames by default and every language has some limit, so for a long linked list or a big grid use a loop or an explicit stack.

Practice

More problems to try on your own.