Recursive step

Break the problem into a smaller same-shape problem.

Recursion vs loop

Many recursion problems can also be solved with a loop. Recursion may be more readable but each call uses stack space.

Loops generally use less memory. Recursion makes it easier to think by dividing the problem.

Call stack

Each recursive call adds a frame to the stack. When the base case is reached, calls unwind and each frame returns its result.

Very deep recursion can cause stack overflow. That is why loops are preferred for very large inputs.

Exercise Array length (recursive)

Write length_recursive(arr). If empty return 0, else 1 + length_recursive(arr[1:]). Print 4 with print(length_recursive([4, 5, 6, 7])).

Show example solution

def length_recursive(arr):
    # Compute length
    if len(arr) == 0:
        return 0
    return 1 + length_recursive(arr[1:])
print(length_recursive([4, 5, 6, 7]))

Test yourself

Recursive step: match the terms

Recursion

Uses stack
Loop

Less memory
Stack overflow

Too deep
Base case

Stops
What does recursion use that loops do not?
- Stack space
- Loop
- Hash table
- Tree
Show answer

Stack space — Recursion uses stack space.

Stack overflow

Very deep recursion causes ____.

Show answer

Very deep recursion causes stack overflow.

Next lesson: Summary - Recursion

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies