Wolfram Demonstrations Project

12,000+ Open Interactive Demonstrations
Powered by Notebook Technology »

Iteration versus Recursion in the Fibonacci Sequence

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

The Fibonacci sequence is defined by , .

[more]

To calculate , say, you can start at the bottom with , then , and so on. This is the iterative method.

Alternatively, you can start at the top with , working down to reach and . 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.

[less]

Contributed by: Ann Rajan (June 2016)
Special thanks to the University of Illinois NetMath Program and the mathematics department at William Fremd High School.
Open content licensed under CC BY-NC-SA

Snapshots

Details

Snapshot 1: iterative and recursive tree plots for

Snapshot 2: same for

Snapshot 3: same for

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.

Embed Code

Take advantage of the Wolfram Notebook Emebedder for the recommended user experience.

Related Demonstrations More by Author
Browse all topics
Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send