Python Programming

Remember Fibonacci sequence from Lesson 6?

As a reminder, the Fibonacci sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … The first numbers are 0 and 1, and then each subsequent number is the sum of the two preceding numbers.

In Lesson 6, you have implemented an iterative version of the code. I’m sure you implemented it and did not skip it, did you? 🥺

Now, you will implement a recursive version of a Fibonacci number generator.

To simplify the problem a bit (so that you can concentrate on practising recursion), your function fibonacci() should take a positive integer position as input, and return an int containing the Fibonacci number at the given position (starting from zero 0).

For example:

• if the input is 0, the function should return 0.
• if the input is 1, the function should return 1.
• if the input is 2, the function should return 1 (0+1).
• if the input is 3, the function should return 2 (1+1).
• if the input is 4, the function should return 3 (1+2).
• if the input is 5, the function should return 5 (2+3).
• if the input is 6, the function should return 8 (3+5).
• etc.

Remember to test your program to make sure it works!

Again, think carefully about the problem on a piece of paper first before trying to implement anything! What is/are the base case(s)? What is/are the recursive case(s)?

Sample usage

>>> fibonacci(3)
2
>>> fibonacci(6)
8
>>> fibonacci(9)
34
>>> fibonacci(1)
1
>>> fibonacci(0)
0