Algorithms For Dummies

  Relying on Dynamic Programming 

     303

Caching  is  another  term  that  you  find  used  when  talking  about  memoization. 

Caching refers to using a special area of computer memory to serve data faster 

when required, which has more general uses than memoization.

To be effective, dynamic programming needs problems that repeat or retrace pre-

vious steps. A good example of a similar situation is using recursion, and the 

landmark of recursion is calculating Fibonacci numbers. The Fibonacci sequence 

is simply a sequence of numbers in which the next number is the sum of the pre-

vious two. The sequence starts with 0 followed by 1. After defining the first two 

elements, every following number in the sequence is the sum of the previous ones. 

Here are the first eleven numbers:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

As with indexing in Python, counting starts from the zero position, and the last 

number in the sequence is the tenth position. The inventor of the sequence, the 

Italian mathematician Leonardo Pisano, known as Fibonacci, lived in 1200. Fibo-

nacci thought that the fact that each number is the sum of the previous two should 

have made the numbers suitable for representing the growth patterns of a group 

of rabbits. The sequence didn’t work great for rabbit demographics, but it offered 

unexpected insights into both mathematics and nature itself because the numbers 

appear in botany and zoology. For instance, you see this progression in the 

branching of trees, in the arrangements of leaves in a stem, and of seeds in a sun-

flower  (you  can  read  about  this  arrangement  at 

https://www.goldennumber.

net/spirals/

).

Fibonacci was also the mathematician who introduced Hindu-Arabic numerals to 

Europe, the system we daily use today. He described both the numbers and the 

sequence in his masterpiece, the Liber Abaci, in 1202.

You can calculate a Fibonacci number sequence using recursion. When you input a 

number, the recursion splits the number into the sum of the previous two Fibo-

nacci  numbers  in  the  sequence.  After  the  first  split,  the  recursion  proceeds  by 

performing the same task for each element of the split, splitting each of the two 

numbers into the previous two Fibonacci numbers. The recursion continues split-

ting numbers into their sums, until it finally finds the roots of the sequence, the 

numbers 0 and 1. Reviewing the two types of dynamic programming algorithm 

described in the previous paragraph, this solution uses a top-down approach. The 

following code shows the recursive approach in Python. (You can find this code in 

the 

A4D; 16; Fibonacci.ipynb

 file on the Dummies site as part of the download-

able code; see the Introduction for details.)

 def fib(n, tab=0):

    if n==0:

        return 0

---

304