Base/recursive/combine, memoization, iterative conversion.

Recursion — Elegant, Until It's a Stack Overflow

Recursion solves problems by reducing them to smaller versions of the same problem. Every recursive function has a base case (terminates), a recursive case (calls itself with smaller input), and a combine step (merges results). .NET does not reliably tail-call optimise, so deep recursion risks StackOverflowException. Converting to an explicit Stack<T> removes the recursion limit. Memoization caches recursive results to avoid exponential recomputation.

Interactive Pipeline Flow

UnderstandImplementOptimise

🛑 Base Case — n == 0 or n == 1

Base case prevents infinite recursion. For Fibonacci: n <= 1 return n. For tree traversal: node == null return.

Architecture Diagrams

Fibonacci without vs with memoization: O(2^n) vs O(n).

Loading diagram...

Key Design Decisions

💾Always memoize overlapping subproblems

If the same input is computed more than once (Fibonacci, grid paths), add a Dictionary<int,int> cache. Instant transformation from exponential to linear.

🔁Convert to iterative for production code

Any recursion over user-controlled depth (file system, JSON, tree) must be iterative with explicit Stack<T> to prevent StackOverflowException.

🛑Always write base cases first

Write the base case before the recursive case. Trace through the simplest input (n=0, n=1) before testing larger inputs.

Discussion