Recursion | AI Pathshala

Definition

Can a function call itself without running forever?

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case, a simple case it answers directly without calling itself, so that the calls eventually stop. Each waiting call is kept on the call stack.

In simple words

5 factorial is 5 × 4 × 3 × 2 × 1. Notice that it is 5 × (4 factorial). So factorial(5) asks factorial(4), which asks factorial(3), down to factorial(1), the base case, which simply says 1. Then the answers multiply back up: 1, 2, 6, 24, 120.

Why it matters

Many problems are naturally recursive: folders inside folders, trees in decision trees, game moves in minimax, and the splitting in fast sorts. Recursion lets you write them in a few clear lines.

How it works

factorial(4)
= 4 × factorial(3)
= 4 × 3 × factorial(2)
= 4 × 3 × 2 × factorial(1)
= 4 × 3 × 2 × 1          ← base case
= 24

In code

Factorial, a countdown, and a sum of a list, each with its base case. The indentation shows how deep the calls go.

recursion.py

def factorial(n, depth=0):
    print("  " * depth + f"factorial({n})")
    if n == 1:                      # base case
        return 1
    return n * factorial(n - 1, depth + 1)

print("Result:", factorial(4))

def countdown(n):
    if n == 0:
        print("Lift off!")
        return
    print(n)
    countdown(n - 1)

countdown(3)

def total(numbers):
    if not numbers:                 # base case: an empty list sums to 0
        return 0
    return numbers[0] + total(numbers[1:])

print("Sum of [4, 8, 15]:", total([4, 8, 15]))

Output

factorial(4)
  factorial(3)
    factorial(2)
      factorial(1)
Result: 24
3
2
1
Lift off!
Sum of [4, 8, 15]: 27

Try it yourself

Order the calls on the call stack

For factorial(3), put the events in the order they happen.

1factorial(1) reaches the base case and returns 1
2factorial(3) is called and waits for factorial(2)
3factorial(3) returns 3 × 2 = 6
4factorial(2) is called and waits for factorial(1)
5factorial(2) returns 2 × 1 = 2

Common mistakes

Forgetting the base case.
Not making the problem smaller in each call, so the base case is never reached.
Using recursion for simple counting that a loop does more clearly.

Check yourself

1. What is a base case?

2. What is factorial(5)?

3. A recursive function with no base case raises…

Summary

A recursive function calls itself on a smaller problem.
A base case stops the calls; results then return back up.
It suits trees, folders and game searches.

Finished reading?

Sources: W3Schools: Python Recursion