Recursion

A function that asks a smaller version of itself for help, until the answer is easy

Imagine you are standing in a long line and you want to know your spot in it. You cannot see the front. So you tap the person ahead of you and ask, "What number are you?"
They do not know either, so they ask the person ahead of them. That question travels all the way to the front. The first person says "I am number 1." Then the answer travels back: 1, 2, 3, and so on, until it reaches you.
That is recursion. Each person did the same tiny thing: ask the one ahead, then add one. Nobody had to see the whole line.

In code, recursion is a function that calls itself on a smaller version of the same problem.
It needs two things, and only two:

A stopping point, the easy case it answers straight away without asking again. (People call this the *base case*.) In our line, that was the first person saying "I am number 1."

A smaller ask, where it hands the rest of the work to a smaller copy of itself. (People call this the *recursive case*.)

Without a stopping point it would ask forever, like a line with no front. So the stopping point is not optional.

The same idea in code: factorialpython

def factorial(n):
    # Base case: 0! = 1
    if n == 0:
        return 1
    # Recursive case: n! = n × (n-1)!
    return n * factorial(n - 1)

# factorial(4) = 4 × factorial(3)
#              = 4 × 3 × factorial(2)
#              = 4 × 3 × 2 × factorial(1)
#              = 4 × 3 × 2 × 1 × factorial(0)
#              = 4 × 3 × 2 × 1 × 1
#              = 24

print(factorial(4))  # → 24

🔍Code TracerStep 1 / 5

trace.py

1def fib(n):

2 if n <= 1: return n←

3 return fib(n-1) + fib(n-2)

5result = fib(4)

Variables

nint

Step 1 / 5

🤔Quick Check

What happens if you forget the stopping point (the base case)?

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Power Function

Implement x raised to the power n using recursion. Use fast exponentiation (halve the problem each time).
Expected output: 8

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next