5️⃣

18.5 Iterative Fibonacci

Iterative Fibonacci

In the previous section, you learned how to find a certain number in the Fibonacci sequence using recursion. However, this solution takes a huge amount of time because, for each number calculated, it needs to calculate the previous numbers more than once. Using iterations rather than recursion is much better in this case since the calculation time will be much less.

# iteration is much quicker than recursion for this problem

# finds the nth term in the Fibonacci sequence using iteration
def iterative_fib(n):
    if n <= 0:
        return None  # base case; out of bounds

    current = 0
    next_term = 1

    for i in range(n - 1):  # this is equivalent to for i in range(1, n)
        current, next_term = next_term, current + next_term
        # this is just a slightly rewritten fib sequence;
        # instead of looking at the past 2 cases, it looks at the
        # current and next terms to determine the next next term

    return current  # will be 0 if n is 1, 1 if n is 2, etc...

print(iterative_fib(5))

View code on GitHub.

This is just one of the numerous examples of when iteration is better than recursion. Next time you code, you should keep in mind that recursion isn't always the right answer. Sometimes, writing a solution iteratively is much better.

Previous Section

Next Section

⚖️

Copyright © 2021 Code 4 Tomorrow. All rights reserved. The code in this course is licensed under the MIT License. If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.