Fibonacci Iterative Recursive
Fast recall
Quick revision
Core answer
Whether you understand Fibonacci Iterative Recursive beyond memorized syntax.
Giving a definition without explaining a practical trade-off.
Connect the concept to a small production example and state its complexity or failure mode.
Interview-ready guide
Interview answer
Both forms, executed:
// Iterative — O(n) time, O(1) space
func fib(n int) int {
if n <= 1 { return n }
a, b := 0, 1
for i := 2; i <= n; i++ {
a, b = b, a+b
}
return b
}
// fib(0..7) → 0 1 1 2 3 5 8 13 — verified
// Naive recursive — O(2^n)
var fibRec func(n int) int
fibRec = func(n int) int {
if n <= 1 { return n }
return fibRec(n-1) + fibRec(n-2)
}
// fibRec(10) → 55 — verified (fast at small n; crawls at 40+)The naive recursion's problem: fibRec(n-1) and fibRec(n-2) each recompute the ENTIRE subtree below them — fib(5) computes fib(2) three times, fib(3) twice. The tree doubles every level: fib(40) is ~10^12 calls.
The iterative solution's mechanics: two variables (a = fib(i-2), b = fib(i-1)); each loop advances one step. The simultaneous assignment (a, b = b, a+b) is Go's clean swap: both RHS values evaluated before assignment.
The memoized recursion (the interview middle ground): store computed values in a map — the recursive shape, O(n) time:
var memo = map[int]int{0: 0, 1: 1}
func fibMemo(n int) int {
if v, ok := memo[n]; ok { return v }
v := fibMemo(n-1) + fibMemo(n-2)
memo[n] = v
return v
}The interview flow: write iterative (the production answer), explain why naive recursion is exponential, show memoization as the technique for 'recursive shape + iterative cost.'
Fibonacci Iterative Recursive
Direct Answer
Iterative: loop with two variables (a, b) — O(n), O(1) space, the right answer. Recursive: fib(n-1) + fib(n-2) — O(2^n) exponential, the naive trap that interviews test. Memoization bridges.
Deep Dive & Architecture
The call-tree arithmetic, concretely: fibRec(n) spawns fibRec(n-1) and fibRec(n-2) — the tree's node count grows as the Fibonacci sequence itself (fib(n) calls ≈ fib(n+1)). fib(40) is ~102 million calls; fib(50) is ~12 billion. The exponential is the worst-case branching factor (2^depth), pruned only by overlapping subtrees.
The memoization's transformation: each memo hit collapses a subtree to an O(1) lookup. The recursion still descends, but each unique n computes once — O(n) unique calls, O(n) map space. The cached form IS the iterative solution wearing a recursive shape.
The tail-recursion note for honesty: Go doesn't optimize tail calls — the iterative loop is not equivalent to a tail-recursive form. The recursive Fibonacci at fibRec(1000) would stack-overflow before it finishes; the iterative runs in microseconds. 'Recursion for shape, iteration for production' is the Go discipline.
Common Mistakes & Pitfalls
Giving a definition without explaining a practical trade-off.
Check your understanding
Answer these without looking back at the article.
- When would you use Fibonacci Iterative Recursive in a real project?
- How would you compare Fibonacci Iterative Recursive with an alternative?
- What is a common mistake when using Fibonacci Iterative Recursive?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.