Recursion, call trees and explicit stacks

Recursion requires a base case, a smaller subproblem and combination logic. Factorial follows n!=n·(n−1)! with 0!=1. Reject negative inputs so the process cannot move away from its base case. Active frames consume space; Python does not guarantee tail-call elimination.

Naive Fibonacci repeatedly solves identical subproblems. Its call tree may contain exponentially many calls while its maximum active stack depth is O(n). Memoisation removes repeated subproblems; iteration can also remove the call stack.

Recursive tree DFS is readable but a long chain may exceed stack limits. An explicit stack records pending nodes and, if necessary, continuation state. Preorder, inorder and postorder differ in when a node is processed. Prove recursive correctness through induction on the subproblem contract.

def factorial(n):
    if n < 0:
        raise ValueError("negative factorial")
    result = 1
    for x in range(2, n + 1):
        result *= x
    return result
assert factorial(4) == 24