Aim

To generate the first n Fibonacci numbers both iteratively and recursively, and to contrast their time/space complexity and stack behaviour.

Theory

Fibonacci is the canonical playground for comparing iteration against recursion. The iterative version keeps a two-variable sliding window (a, b) and runs in O(n) time, O(1) space. The naive recursive version FibRec(n) = FibRec(n-1) + FibRec(n-2) re-derives the same subproblems exponentially many times — approximately O(φⁿ) calls where φ ≈ 1.618 (the golden ratio), so FibRec(40) already needs over 200 million calls. Each invocation pushes a stack frame (return address, parameter, saved registers) onto the thread's stack (1 MB by default in .NET); deep recursion risks StackOverflowException, which since .NET 2.0 is uncatchable and terminates the process. Memoisation — caching results in an array or Dictionary<int, int> — collapses the call tree to O(n), which is the essence of dynamic programming. Note also that the C# JIT performs no tail-call optimisation here, and the call is not in tail position anyway: the addition executes only AFTER both child calls return, so every frame stays live while its subtree runs.

Requirements

• .NET SDK 8.0+ with the dotnet CLI, or the built-in RUN CODE button.

Procedure

1. Create the project: dotnet new console -n FibLab, cd FibLab, paste the code into Program.cs.
2. Execute dotnet run — both printed sequences must match: 0 1 1 2 3 5 8 13.
3. Raise n to 35 and wrap the recursive loop in a Stopwatch to feel the exponential blow-up first-hand; the iterative half stays instantaneous.

Explanation of the Code

• static int FibRec(int n) — the base case if (n <= 1) return n; anchors the recursion (Fib(0)=0, Fib(1)=1); without it the calls would never terminate.
• return FibRec(n - 1) + FibRec(n - 2); — binary recursion: two self-calls per frame, which is exactly what makes the call count exponential.
• The iterative loop in Main: Console.Write(a + " ") prints BEFORE the slide so the series starts at 0; then int next = a + b; a = b; b = next; advances the two-element window one step.
• Console.WriteLine("\nWith Recursion:") separates the two outputs; the second for loop calls FibRec(i) for i = 0..7, recomputing each prefix from scratch — deliberately wasteful so the contrast with the O(n) loop is visible.

Expected Output

Without Recursion:
0 1 1 2 3 5 8 13
With Recursion:
0 1 1 2 3 5 8 13

(Each number is followed by a space because Console.Write(a + " ") is used instead of WriteLine.)

🎯 Viva Questions

1. Time complexity of naive recursive Fibonacci? — Exponential, O(φⁿ); the iterative version is O(n).
2. What is a stack frame? — Per-call storage for parameters, locals and the return address on the thread's stack.
3. Can you catch StackOverflowException in .NET? — No; since .NET 2.0 it terminates the process outright.
4. What is memoisation? — Caching sub-results so each distinct input is computed once, turning O(φⁿ) into O(n).
5. Why must a recursive method have a base case? — To terminate the call chain; otherwise infinite recursion overflows the stack.
6. Is FibRec tail-recursive? — No; the addition runs after the recursive calls return, so the frame cannot be reused.