Unraveling Recursion: Understanding the Magic Behind It

What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem. It's useful for tasks that can be broken down into smaller, similar sub-problems.

Advantages

• Elegant solutions for some problems. Eg. The Tower of Hanoi puzzle: Move a stack of disks from one peg to another, following specific rules.
• Simplifies complex algorithms. Eg. Merge sort: Divide an array into smaller parts, sort them, then combine.
• Useful for tree-like structures. Eg. Exploring a family tree: Start with a person, then recursively explore their parents, grandparents, etc.

Disadvantages

• Can be memory-intensive. Eg. Calculating Fibonacci numbers recursively: Each call creates new memory allocations, potentially leading to stack overflow for large inputs.
• Sometimes slower than iterative solutions. Eg. Counting backwards from 100 to 1: Recursion would make 100 function calls, while a simple loop is more efficient.
• May be confusing for beginners

Example: Factorial Calculation

Recursive approach

def factorial(n)
  return 1 if n <= 1
  n * factorial(n - 1)
end

Steps:

1. factorial(5) is called
   • 5 > 1, so it returns 5 * factorial(4)
2. factorial(4) is called
   • 4 > 1, so it returns 4 * factorial(3)
3. factorial(3) is called
   • 3 > 1, so it returns 3 * factorial(2)
4. factorial(2) is called
   • 2 > 1, so it returns 2 * factorial(1)
5. factorial(1) is called
   • 1 <= 1, so it returns 1
6. Now we calculate back up:
   • 2 * 1 = 2
   • 3 * 2 = 6
   • 4 * 6 = 24
   • 5 * 24 = 120

Each step waits for the next one to complete before it can finish its calculation.

Converting to iteration

def factorial_iterative(n)
  result = 1
  (1..n).each { |i| result *= i }
  result
end

Steps:

1. result starts at 1
2. Loop begins:
   • i = 1: result = 1 * 1 = 1
   • i = 2: result = 1 * 2 = 2
   • i = 3: result = 2 * 3 = 6
   • i = 4: result = 6 * 4 = 24
   • i = 5: result = 24 * 5 = 120
3. Loop ends, return 120

Each step immediately calculates and updates the result.

Example: Fibonacci Sequence

Recursive approach

def fibonacci(n)
  return n if n <= 1
  fibonacci(n - 1) + fibonacci(n - 2)
end

Steps:

1. fibonacci(5) is called
   • It calls fibonacci(4) + fibonacci(3)
2. fibonacci(4) is called
   • It calls fibonacci(3) + fibonacci(2)
3. fibonacci(3) is called (first time)
   • It calls fibonacci(2) + fibonacci(1)
4. fibonacci(2) is called (first time)
   • It calls fibonacci(1) + fibonacci(0)
5. fibonacci(1) returns 1
6. fibonacci(0) returns 0
7. fibonacci(2) completes: 1 + 0 = 1
8. fibonacci(1) returns 1
9. fibonacci(3) completes: 1 + 1 = 2
10. fibonacci(2) is called again (second time)
    • It calls fibonacci(1) + fibonacci(0)
11. fibonacci(1) returns 1
12. fibonacci(0) returns 0
13. fibonacci(2) completes: 1 + 0 = 1
14. fibonacci(4) completes: 2 + 1 = 3
15. fibonacci(3) is called again (second time)
    • It calls fibonacci(2) + fibonacci(1)
16. Process repeats...
17. Finally, fibonacci(5) completes: 3 + 2 = 5

Notice how fibonacci(3) and fibonacci(2) are calculated multiple times.

Converting to iteration

def fibonacci_iterative(n)
  a, b = 0, 1
  n.times { a, b = b, a + b }
  a
end

Steps:

1. a = 0, b = 1
2. Loop 5 times:
   • 1st iteration: a = 1, b = 0 + 1 = 1
   • 2nd iteration: a = 1, b = 1 + 1 = 2
   • 3rd iteration: a = 2, b = 1 + 2 = 3
   • 4th iteration: a = 3, b = 2 + 3 = 5
   • 5th iteration: a = 5, b = 3 + 5 = 8
3. Return a, which is 5

Each step builds on the previous result without repeating calculations.

Key points

• Function calls: Each time a function calls itself, it's like starting a new task before finishing the current one. This takes up memory and time.
• Repetition: Recursive functions often repeat the same calculations, while iterative functions typically don't.
• Memory usage: Recursive functions keep information for each call in memory. Iterative functions usually use a fixed amount of memory regardless of input size.
• Predictability: Iterative functions are more predictable in terms of how long they'll take and how much memory they'll use.
• Readability: Sometimes recursive functions are easier to understand, but their performance can be worse.
• The iterative version is much faster, especially for larger numbers, because it doesn't repeat calculations.
• The recursive approach repeatedly calculates the same values, leading to many function calls and repeated work.
• The iterative approach calculates each value once, building on previous results, which is more efficient.

Tail recursion (optimized recursion)

def fibonacci_tail(n, a = 0, b = 1)
  return a if n == 0
  fibonacci_tail(n - 1, b, a + b)
end

This is a special type of recursion that some computers can turn into iteration automatically. It's like leaving yourself a note before climbing each step of the ladder, so you don't have to climb back down. However, not all programming languages or computers can do this automatically, so iteration is often still preferred.

In general, iteration is often better for performance because:

• It uses less memory - you're not piling up function calls.
• It's usually faster - you're not repeating work you've already done.
• It's more predictable - you won't suddenly run out of memory for large inputs.

Remember, for small inputs, you might not notice a difference. But as inputs get larger, these performance improvements become more important.

Key points for converting recursion to iteration

• Use loops (while, for, etc.) instead of recursive calls
• Implement a stack or state variables to track progress
• Identify the base case and use it as a loop termination condition

When to use recursion

• Tree traversal
• Divide-and-conquer algorithms
• Problems with a naturally recursive structure

When to avoid recursion

• Performance-critical code
• Problems with simple iterative solutions
• When stack overflow is a concern