Iterative vs Recursive

Any problem that can be solved recursively can also be solved iteratively (using loops). So, which one should you choose?

1. The Trade-off

Feature	Recursion	Iteration
Code Style	Elegant, cleaner for tree/graph problems.	Can be verbose, requires manual state management.
Memory Usage	High (O(n) stack space).	Low (O(1) space usually).
Performance	Slower (function call overhead).	Faster (CPU optimized loops).
Risk	Stack Overflow if too deep.	Infinite loops (easier to debug).

2. Code Comparison: Factorial

Let’s look at the same algorithm implemented both ways.

Recursive Implementation

Pros: Very readable, direct translation of math formula. Cons: O(n) space complexity due to call stack.

// Java - Recursive
public int factorial(int n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

Iterative Implementation

Pros: O(1) space complexity. No stack overflow risk. Cons: Slightly more code (loop variables).

// Go - Iterative
func Factorial(n int) int {
  result := 1
  for i := 2; i <= n; i++ {
    result *= i
  }
  return result
}

3. Tail Recursion

Tail Recursion is a special case where the recursive call is the very last action in the function.

In standard recursion, you do return n * factorial(n-1). The multiplication happens after the recursive call returns. In tail recursion, you do return factorial(n-1, n * accumulator). The calculation happens before the call.

Why it matters: Some compilers (like in C++, Scala, or Haskell) can optimize tail recursion into a loop, eliminating the stack overhead. Note: Java and Python do not support Tail Call Optimization (TCO), so tail recursion still uses stack space. Go also does not currently support TCO.

Tail Recursive Example (Concept)

// Java - Tail Recursive Style (still uses stack in Java)
public int factorialTail(int n, int accumulator) {
  if (n <= 1) return accumulator;
  return factorialTail(n - 1, n * accumulator);
}

4. Converting Recursion to Iteration

If you hit a StackOverflowError, you can convert any recursive algorithm to an iterative one by manually using a Stack data structure.

1. Create an empty Stack.
2. Push the initial parameters.
3. While Stack is not empty:
   • Pop parameters.
   • Process logic.
   • Push new parameters for “recursive” calls.

[!TIP] For simple recursion (like Factorial or Fibonacci), a simple loop is enough. For complex recursion (like Tree Traversal), a manual Stack is often needed to mimic the Call Stack.

---

Module Conclusion

You’ve mastered the basics! You know what an algorithm is, how to measure its efficiency with Big O, and the trade-offs between recursion and iteration.

---

5. Deep Dive Strategy Lab: Iterative Vs Recursive

Intuition Through Analogy

Think of this chapter like debugging a production outage timeline. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?