Recursion

Part of the free LogicWiz Python course, Pack B: College Semester Pack. The examples and practice run in the app.

Your lab record says "Write a recursive program for factorial, Fibonacci and Tower of Hanoi", and the external examiner will ask you to trace it in the viva. A function that calls itself sounds like a loop that never ends. It ends, if you know the one rule.

You'll learn to

• Write a recursive function with a base case and a smaller recursive case
• Trace the call stack on paper, the way the viva asks
• Solve the lab classics: factorial, Fibonacci, Tower of Hanoi, sum of digits, recursive binary search
• Spot the two bugs: a missing base case and a missing `return`

Learn

Two parts, always

A recursive function solves a problem by calling itself on a smaller piece of the same problem.

1. Base case: the smallest version, answered directly, with no more calls. (0! = 1)
2. Recursive case: shrink the problem and trust the call to solve the rest. (n! = n × (n-1)!)

Every call must move towards the base case. If it doesn't, the calls never stop and Python gives up with RecursionError after about 1000 levels.

Factorial, step by step

def fact(n):
    if n == 0:              # base case
        return 1
    return n * fact(n - 1)  # recursive case: a smaller n


print(fact(4))
print(fact(0))

Step through it. fact(4) cannot finish until fact(3) returns, which waits for fact(2), and so on down to fact(0).

The call stack (draw this in the viva)

Each call gets its own box on the call stack, with its own n. Going down, calls wait; coming back up, each one finishes its multiplication.

fact(4) = 4 * fact(3)          waiting
  fact(3) = 3 * fact(2)        waiting
    fact(2) = 2 * fact(1)      waiting
      fact(1) = 1 * fact(0)    waiting
        fact(0) = 1            base case: return 1
      fact(1) = 1 * 1 = 1      return 1
    fact(2) = 2 * 1 = 2        return 2
  fact(3) = 3 * 2 = 6          return 6
fact(4) = 4 * 6 = 24           return 24

5 calls, 5 boxes on the stack at the deepest point. That memory is why recursion can be slower than a loop.

No base case: RecursionError

def countdown(n):
    if n % 250 == 0:
        print("still going, n =", n)
    countdown(n - 1)        # never stops: no base case


countdown(500)

n goes 500, 499, ... 0, -1, -2 ... and never stops, until the stack is full (about 1000 calls) and Python raises RecursionError. Add if n == 0: return at the top and it stops.

Fibonacci: beautiful but slow, then fast

from functools import lru_cache

calls = 0


def fib(n):
    global calls
    calls += 1
    if n < 2:               # fib(0) = 0, fib(1) = 1
        return n
    return fib(n - 1) + fib(n - 2)


print(fib(20), "took", calls, "calls")


@lru_cache(maxsize=None)    # remember answers already worked out
def fast_fib(n):
    if n < 2:
        return n
    return fast_fib(n - 1) + fast_fib(n - 2)


print(fast_fib(80))

Plain fib(20) makes 21,891 calls because it solves fib(18) twice, fib(17) three times... Remembering results (memoisation, Module 11) makes fib(80) instant.

Tower of Hanoi

def hanoi(n, src, aux, dst):
    if n == 1:
        print(f"Move disk 1 from {src} to {dst}")
        return
    hanoi(n - 1, src, dst, aux)      # 1. park n-1 disks on the spare rod
    print(f"Move disk {n} from {src} to {dst}")   # 2. move the biggest
    hanoi(n - 1, aux, src, dst)      # 3. bring the n-1 disks on top


hanoi(3, "A", "B", "C")

You never think about all the moves. You only say: "move n-1 out of the way, move the big one, move n-1 back on top". For n disks it takes 2**n - 1 moves: 7 for 3 disks.

Recursive binary search

def bsearch(arr, target, lo, hi):
    if lo > hi:                       # base case: nothing left to search
        return -1
    mid = (lo + hi) // 2
    print(f"look at index {mid} ({arr[mid]})")
    if arr[mid] == target:
        return mid
    if target < arr[mid]:
        return bsearch(arr, target, lo, mid - 1)   # left half
    return bsearch(arr, target, mid + 1, hi)       # right half


rolls = [3, 8, 15, 21, 34, 42, 57, 66, 78]
print("found at", bsearch(rolls, 57, 0, len(rolls) - 1))

Each call throws away half the list, so even 1000 items need only about 10 calls. Lesson B2 does the loop version.

Lab mapping. Recursion programs appear in the first-year Python lab lists of VTU, Anna University (GE3171), JNTU, AKTU, DU and Mumbai University: factorial, Fibonacci series, GCD, sum of digits, Tower of Hanoi, and recursive binary search.

Viva questions: "What is a base case?" "What happens without one?" (RecursionError, stack overflow) "Recursion or loop, which is faster?" (a loop: no call overhead) "How many moves for Hanoi with n disks?" (2^n - 1). Be ready to draw the call stack for fact(3).

In one line

Recursion = a base case answered directly + a call on a smaller problem; always return the recursive call; memoise repeated work (@lru_cache).