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