Get startedGet started for free

Fibonacci sequence

In this exercise, you will implement the Fibonacci sequence, which is ubiquitous in nature. The sequence looks like this: "0, 1, 1, 2, 3, 5, 8…". You will create a recursive implementation of an algorithm that generates the sequence.

The first numbers are 0 and 1, and the rest are the sum of the two preceding numbers.

We can define this sequence recursively as: \(fib(n)=fib(n-1)+fib(n-2)\), with \(fib(0)=0\) and \(fib(1)=1\), being \(n\) the \(nth\) position in the sequence.

In the first step, you will code Fibonacci using recursion. In the second step, you will improve it by using dynamic programming, saving the solutions of the subproblems in the cache variable.

This exercise is part of the course

Data Structures and Algorithms in Python

View Course

Hands-on interactive exercise

Have a go at this exercise by completing this sample code.

def fibonacci(n):
  # Define the base case
  if ____ <= ____:
    return n
  else:
    # Call recursively to fibonacci
    ____
    
print(fibonacci(6))
Edit and Run Code