Week 3: Advanced Exercises

Advanced exercises are designed for advanced learners that are ready to take on extra challenges. These exercises are made accessible to all after the class. Note that these exercises typically require more knowledge than what was presented in class.

Adv Exercise: Finding Fibonacci numbers by recursion

Fibonacci

A number in a Fibonacci sequence is defined by the sum of the previous two numbers before it. The sequence starts with initial terms F(1)=1, and F(2)=1. See example below:

# F(n-2) + F(n-1) = F(n)
# F(1) + F(2) = F(3)
# F(2) + F(3) = F(4)
# F(3) + F(4) = F(5)
# F(4) + F(5) = F(6)

1 + 1 = 2
1 + 2 = 3
2 + 3 = 5
3 + 5 = 8

For a more detailed definition of Fibonacci numbers, refer to its Wikipedia page: https://en.wikipedia.org/wiki/Fibonacci_number

Recursion

In simple terms, a recursive function is a function that can call itself. Writing recursive functions require a bit more thought than usual, as your function needs to be able to handle its own output as input!

Read this for more info and exapmles on writing recursive functions: https://www.educba.com/recursive-function-in-python/

If the concept of recursion itself intrigues you, take a look at this Wikipedia page: https://en.wikipedia.org/wiki/Recursion_(computer_science)

Fibonacci and recursion

Finding the `N`th Fibonacci number requires finding the `(N-1)`th and `(N-2)`th number. And to find these numbers, you would need to find the previous numbers that lead to them, eventually tracing your way up to the first two ones in the sequence. If you’ve did your reading on recursion above, you should notice that finding the next Fibonacci number is quite a recursive process.

Do the following:

  1. Write a recursive function to find the `N`th Fibonacci number.

  2. Write a recursive function to find all Fibonacci numbers up to N.

Hints:

  1. Task i is solvable in <5 lines of code.

  2. Task ii is trickier than it seems. Once recursion gets from N to the first two Fibonacci numbers, you need to collect and pass the found Fibonacci numbers all the way back to calculations of the Nth number!

  3. General guidelines the instructors personally found useful in writing recursive functions:

    1. Write a function that carries out the recursion without considering the base condition, i.e. when the recursion stops.

    2. Write another function that only considers the base condition.

    3. Merge both functions into one.

Adv Exercise: Solve Tower of Hanoi

Warning

Training wheels off! The material in today’s class is enough to solve this problem, but will take significant effort.

Tower of Hanoi is a popular game where there are three rods and a stack of disks on the leftmost rod. The goal of the game is to transfer all the disks to the rightmost rod. You can only move one disk at a time, and only smaller disks can be stacked on top of bigger disks. This game would be trivial if the disks were stacked with the smallest disks at the bottom and the largest disks at the top, however this game is interesting precisely because it is the opposite.

Write a function that can solve Tower of Hanoi for any number of disks. You are welcome to refer to its [wikipedia page](https://en.wikipedia.org/wiki/Tower_of_Hanoi).