19.2 - Recursion

• A recursive function is one that calls itself during execution.
• It must have:
  • A base case - the condition where recursion stops.
  • A general (recursive) case - where the function calls itself with updated parameters
• Without a base case, recursion would continue indefinitely and cause a stack overflow
• In programming, recursion is defined just like a normal function, but the function includes a call to itself.
• Advantages:
  • Simpler and cleaner code
  • Ideal for structures like trees, graphs
  • Easier to understand conceptually
  • Reduces the need for extra variables or loops
• Disadvantages
  • Higher memory usage
  • Slower execution
  • Risk of stack overflow
  • Difficult to trace or debug
• What the Compiler Does with Recursive Code
  • The compiler allocates a new memory frame on the call stack for each recursive call.
  • Each frame stores:
    • Function parameters
    • Return address
    • Local variables
  • When the base case is reached, the compiler returns values and removes frames one by one - this is known as stack unwinding
• Stacks and Unwinding
  • Each recursive call is pushed onto the stack.
  • When a call completes, it is popped off the stack.
  • This process continues until the first (initial) call is completed.
  • The stack structure ensures that functions return in the reverse order of their calls: Last In, First Out (LIFO).
• Tracing Recursive Algorithms
  • Tracing involves following the sequence of function calls until the base case is reached.
  • Each recursive call is placed on the call stack
  • Once the base case is reached, the program unwinds the stack, returning values step by step.

Examples of Recursion

No output yet.

factorial(3)
→ 3 * factorial(2)
    → 2 * factorial(1)
        → 1 * factorial(0)
            → returns 1

No output yet.

sum_n(5)
→ 5 + sum_n(4)
    → 4 + sum_n(3)
        → 3 + sum_n(2)
            → 2 + sum_n(1)
                → returns 1