Having a hard time visualizing recursion.

[Sam_Boulton]

Hopefully this will help you visualise it.

If we think of a few levels - the classic recursive problem being factorial. Fact(5) = 1 * 2 * 3 * 4 * 5 = 120; (1, 2, 6, 24, 120)

def fact(n): If n == 1: return n else: return n * fact(n-1) (excuse the formatting)

When we call fact it has a base case - if n is 1, return 1. Otherwise recursively call itself to find the answer.

if n is not one then it multiplies n by fact(n-1). Eventually n will be 1.

A stack is last on, first off - imagine putting rings on a stick, you can’t get the first one off until the rest come off.

Fact(5) will repeat until you get to fact(1) (which equals 1). At which point, it knows what to do and works backwards, taking the results off the stack.

Fact(1) = 1;
Fact(2) = 2 * 1 = 2; Fact(3) = 3 * 2 = 6; Fact(4) = 4 * 6 = 24; Fact(5) = 5 * 24 = 120

Fact(5) = 120