Iteration versus Recursion in the Fibonacci Sequence

​
Fibonacci number
2
The Fibonacci sequence
f
n
is defined by
f
0
=
f
1
=1
,
f
n
=
f
n-1
+
f
n-2
.
To calculate
f
5
, say, you can start at the bottom with
f
2
=
f
0
+
f
1
=1+1=2
, then
f
3
=
f
2
+
f
1
=2+1=3
, and so on. This is the iterative method.
Alternatively, you can start at the top with
f
5
=
f
4
+
f
3
=(
f
3
+
f
2
)+(
f
3
+
f
1
)=…
, working down to reach
f
0
and
f
1
. This is the recursive method.
The graphs compare the time and space (memory) complexity of the two methods and the trees show which elements are calculated.

Details

Snapshot 1: iterative and recursive tree plots for
n=3
Snapshot 2: same for
n=10
Snapshot 3: same for
n=6

References

[1] T. Cormen et al., Introduction to Algorithms, 3rd ed., Cambridge: The MIT Press, 2009.
[2] E. Lantzman, "Iterative vs. Recursive Approaches." Code Project (blog). (Jun 14, 2016) www.codeproject.com/Articles/21194/Iterative-vs-Recursive-Approaches.

External Links

Fibonacci Tree
Big-O Notation (Wolfram MathWorld)
Call Graphs of Fibonacci-Like Functions
Time Complexity of Common Sorting Algorithms

Permanent Citation

Ann Rajan
​
​"Iteration versus Recursion in the Fibonacci Sequence"​
​http://demonstrations.wolfram.com/IterationVersusRecursionInTheFibonacciSequence/​
​Wolfram Demonstrations Project​
​Published: June 16, 2016