Recursion and Iteration Overview

Overview

This lecture explains recursion in programming, contrasts it with iteration, demonstrates both approaches using the factorial function, and highlights their advantages and limitations.

What is Recursion?

• Recursion is when a function (or subroutine) calls itself from within its own code.
• A recursive function must have a stopping condition (base case) to prevent infinite calls.
• For non-base cases, the function calls itself with a modified input.
• The stopping condition should be reachable in a finite number of steps to avoid stack overflow errors.

Factorial Example: Iterative vs Recursive

• Factorial of a non-negative integer n (written n!) is the product of all positive integers ≤ n.
• Iterative approach uses loops (e.g., for loop) and accumulates the result in a variable.
• Recursive approach defines factorial so that n! = n × (n-1)!, with the base case 0! = 1.
• Each recursive call creates a new function instance, with values stored on the call stack.

How Recursive Functions are Processed

• Each function call pushes local variables and a return address onto its stack.
• The stack grows with each recursive call until the base case is reached.
• Once the base case returns, the stack unwinds and each call returns its computed value up the chain.

Efficiency and Limitations

• Recursive solutions typically use more memory since each call adds a new stack frame.
• Iterative solutions (using loops) are generally more memory efficient for tasks like factorial.
• Excessive recursion depth can cause stack overflow errors and program crashes.
• Recursion is sometimes necessary, such as in tree traversal or flood fill algorithms.

Key Terms & Definitions

• Recursion — A programming technique where a function calls itself.
• Base case (Stopping condition) — The condition that ends the recursive calls.
• Stack overflow — Error that occurs when the call stack exceeds its limit.
• Iteration — Repeating steps using loops (e.g., for, while) instead of function calls.
• Call stack — The memory structure that tracks active subroutine calls and local variables.

Action Items / Next Steps

• Practice writing and tracing both recursive and iterative functions for factorial.
• Reflect: When would recursion be preferable over iteration?
• Review tree traversal and flood fill algorithms for more examples of recursion.