Computer Science – 19.2 Recursion | e-Consult

The function factorial(n) calculates the factorial of a non-negative integer n using recursion.

Base Case: The base case is if n == 0: return 1. This is essential to stop the recursion. When n is 0, the function immediately returns 1, without making any further recursive calls.

Recursive Step: The recursive step is else: return n * factorial(n-1). Here, the function returns the product of n and the factorial of n-1. This breaks the problem down into a smaller, similar subproblem. The function calls itself with a smaller input (n-1) until it reaches the base case.

Call Stack: Each time the function calls itself, a new frame is added to the call stack. This frame stores the local variables (like n) and the return address (where to go back to after the recursive call completes). For example, if we call factorial(3), the call stack will evolve as follows:

• factorial(3) is called. It returns 3 * factorial(2). A frame is added to the stack for factorial(3).
• factorial(2) is called. It returns 2 * factorial(1). A frame is added to the stack for factorial(2).
• factorial(1) is called. It returns 1 * factorial(0). A frame is added to the stack for factorial(1).
• factorial(0) is called. It returns 1 (base case). A frame is added to the stack for factorial(0).
• Now, factorial(1) can complete its calculation (1 * 1 = 1) and return 1 to factorial(2). The factorial(1) frame is removed from the stack.
• factorial(2) can complete its calculation (2 * 1 = 2) and return 2 to factorial(3). The factorial(2) frame is removed from the stack.
• Finally, factorial(3) can complete its calculation (3 * 2 = 6) and return 6. The factorial(3) frame is removed from the stack.

The call stack unwinds, with each frame being removed as the recursive calls return. This process continues until the initial call to factorial(n) completes and returns the final result.