Loading PyCodeIt workspace...
Recursion solves complex problems by breaking them down into smaller sub-problems of the exact same type until reaching a base case. Tracing the call stack (`winding phase during recursive calls and unwinding phase during returns`) is critical for dynamic programming and tree algorithms.
Theoretical Blueprint:Tracing recursion is like stacking dinner plates on a spring-loaded cafeteria dispenser (`Winding`). When you reach the last plate (`Base Case`), you begin popping the plates off one by one from the top down (`Unwinding`).
Common Developer Trap:Beginners often forget that statements written AFTER the recursive function call execute only during the stack **unwinding** phase (`in reverse order`).
def countdown(n):
if n <= 0:
return
print(n, end=' ')
countdown(n - 1)
print(n, end=' ')
countdown(3)3 2 1 1 2 3 Winding phase prints `3 2 1`. At `n=0`, base case returns. Unwinding phase pops stack frames in reverse order (`1 -> 2 -> 3`), printing `1 2 3`. Combined: `3 2 1 1 2 3 `.
def sum_digits(n):
if n < 10:
return n
return n % 10 + sum_digits(n // 10)
print(sum_digits(456))15`sum_digits(456)` evaluates `6 + sum_digits(45) -> 6 + 5 + sum_digits(4)`. Base case `sum_digits(4)` returns `4`. Summing `6 + 5 + 4 = 15`.
def rev(s):
if len(s) <= 1:
return s
return rev(s[1:]) + s[0]
print(rev('Cat'))taCCalls: `rev('Cat') -> rev('at') + 'C' -> rev('t') + 'a' + 'C' -> 't' + 'a' + 'C' = 'taC'`.
def is_even(n):
if n == 0: return True
return is_odd(n - 1)
def is_odd(n):
if n == 0: return False
return is_even(n - 1)
print(is_even(3), is_odd(3))False True`is_even(3)` chains down to `is_odd(0)`, which returns `False`. `is_odd(3)` chains down to `is_even(0)`, which returns `True`. Output: `False True`.