What is recursion?

Recursion occurs when a function calls itself repeatedly, usually with slightly modified arguments, until it reaches a base condition (a stopping point). Then, it starts to "unwind" by resolving each function call step by step, returning a final result.

def fact(n):
    if n == 0 or n == 1:
        return 1
    return n * fact(n - 1)

res = fact(5)
print(res)

Explanation step-by-step

fact(5) checks if 5 == 0 or 5 == 1 → False

Then it executes return 5 * fact(4). Now, to get this result, we must calculate fact(4) first.

fact(4) checks if 4 == 0 or 4 == 1 → False

Then executes return 4 * fact(3). Now we must find fact(3).

.......

fact(1) checks if 1 == 0 or 1 == 1 → True, base case reached!

It returns 1 immediately.

1. fact(1) returns 1 to fact(2)

2. fact(2) returns 2 * 1 = 2 to fact(3)

3. fact(3) returns 3 * 2 = 6 to fact(4)

4. fact(4) returns 4 * 6 = 24 to fact(5)

5. fact(5) returns 5 * 24 = 120

Where is the value stored?

Recursive calls use the call stack, a special region of memory where functions and their local variables are stored temporarily. Each recursive call adds a new stack frame to the stack.

fact(5)
 └─5 * fact(4)
     └─4 * fact(3)
         └─3 * fact(2)
             └─2 * fact(1)
                 └─1 (base case reached)