DSA Recursion

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem.

The Idea

Imagine you are in a long queue and want to know your position. You ask the person in front: "What is your position?" They ask the person in front of them, and so on. The first person says "1". Each person then adds 1 and passes the answer back. That is recursion.

Every recursive function needs two parts:

Countdown

def countdown(n):
    if n == 0:          # base case
        print("Go!")
        return
    print(n)
    countdown(n - 1)    # recursive case

countdown(3)

3
2
1
Go!

Factorial

The factorial of n (written n!) is n × (n-1) × ... × 1. For example 4! = 4 × 3 × 2 × 1 = 24. Notice that 4! = 4 × 3!, which is a smaller version of the same problem.

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(4))
print(factorial(10))

24
3628800

How the Call Stack Works

Each call waits for the call inside it to finish. The computer keeps these waiting calls on the call stack:

factorial(4) = 4 * factorial(3)
               factorial(3) = 3 * factorial(2)
                              factorial(2) = 2 * factorial(1)
                                             factorial(1) = 1

Then the answers come back up: 1, then 2 × 1 = 2, then 3 × 2 = 6, then 4 × 6 = 24.

Recursion on a List

The sum of a list is the first item plus the sum of the rest:

def list_sum(items):
    if not items:
        return 0
    return items[0] + list_sum(items[1:])

def reverse_text(s):
    if len(s) <= 1:
        return s
    return reverse_text(s[1:]) + s[0]

print(list_sum([5, 10, 15]))
print(reverse_text("Karachi"))

30
ihcaraK

Fibonacci and Memoization

In the Fibonacci series, each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13...

The simple recursive version is very slow, about O(2^n), because it calculates the same values again and again. Memoization saves each answer the first time, making it O(n).

def fib_slow(n):
    if n < 2:
        return n
    return fib_slow(n - 1) + fib_slow(n - 2)

memo = {}
def fib_fast(n):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_fast(n - 1) + fib_fast(n - 2)
    return memo[n]

print(fib_slow(10))
print(fib_fast(80))

55
23416728348467685

fib_slow(80) would take years to finish. fib_fast(80) finishes instantly.

Recursion or Loop?

• Any recursion can also be written with a loop
• Loops use less memory, because there is no call stack to grow
• Recursion is clearer for problems that split into smaller copies of themselves, such as trees, merge sort and quick sort

Exercise