11.4 Recursive Fibonacci Series Example

• Fibonacci series, begins with 0 and 1 and has the property that each subsequent Fibonacci number is the sum of the previous two

  0, 1, 1, 2, 3, 5, 8, 13, 21, …

• This series occurs in nature and describes a form of spiral
• Ratio of successive Fibonacci numbers converges on a constant value of 1.618…
  • Called the golden ratio or the golden mean
• Humans tend to find the golden mean aesthetically pleasing
  • Architects often design windows, rooms and buildings whose length and width are in the ratio of the golden mean
  • Postcards often are designed with a golden-mean length-to-width ratio

11.4 Recursive Fibonacci Series Example (cont.)

• Defined recursively as follows:

  fibonacci(0) is defined to be 0
  fibonacci(1) is defined to be 1
  fibonacci(n) = fibonacci(n – 1) + fibonacci(n – 2)

• Two base cases
  • fibonacci(0) is 0, and
  • fibonacci(1) is 1.

Function fibonacci

• Initial call to function fibonacci is not a recursive call
• All subsequent calls from function fibonacci’s block are recursive
• Each call immediately tests for the base cases
  • n equal to 0 or n equal to 1
  • If so, returns n, because fibonacci(0) is 0 and fibonacci(1) is 1
• n greater than 1 generates two recursive calls for slightly smaller problems than the original call

def fibonacci(n):
    if n in (0, 1):  # base cases
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

Testing Function fibonacci

for n in range(41):
    print(f'Fibonacci({n}) = {fibonacci(n)}')

Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(4) = 3
Fibonacci(5) = 5
Fibonacci(6) = 8
Fibonacci(7) = 13
Fibonacci(8) = 21
Fibonacci(9) = 34
Fibonacci(10) = 55
Fibonacci(11) = 89
Fibonacci(12) = 144
Fibonacci(13) = 233
Fibonacci(14) = 377
Fibonacci(15) = 610
Fibonacci(16) = 987
Fibonacci(17) = 1597
Fibonacci(18) = 2584
Fibonacci(19) = 4181
Fibonacci(20) = 6765
Fibonacci(21) = 10946
Fibonacci(22) = 17711
Fibonacci(23) = 28657
Fibonacci(24) = 46368
Fibonacci(25) = 75025
Fibonacci(26) = 121393
Fibonacci(27) = 196418
Fibonacci(28) = 317811
Fibonacci(29) = 514229
Fibonacci(30) = 832040
Fibonacci(31) = 1346269
Fibonacci(32) = 2178309
Fibonacci(33) = 3524578
Fibonacci(34) = 5702887
Fibonacci(35) = 9227465
Fibonacci(36) = 14930352
Fibonacci(37) = 24157817
Fibonacci(38) = 39088169
Fibonacci(39) = 63245986
Fibonacci(40) = 102334155

Analyzing the Calls to Function fibonacci

• Evaluation of fibonacci(3)

Complexity Issues

• Caution about recursive programs
• Each non-base-case invocation of fibonacci results in two more recursive calls
• This set of recursive calls rapidly gets out of hand
• fibonacci(20) requires 21,891 calls
• fibonacci(30) requires 2,692,537 calls!
• Each consecutive Fibonacci number you calculate results in a substantial increase in calculation time and in the number of calls
• fibonacci(31) requires 4,356,617 calls
• fibonacci(32) requires 7,049,155 calls!
• Problems of this nature can humble even the world’s most powerful computers
• Avoid Fibonacci-style recursive programs, because they result in an exponential “explosion” of function calls

---

©1992–2020 by Pearson Education, Inc. All Rights Reserved. This content is based on Chapter 5 of the book Intro to Python for Computer Science and Data Science: Learning to Program with AI, Big Data and the Cloud.

DISCLAIMER: The authors and publisher of this book have used their best efforts in preparing the book. These efforts include the development, research, and testing of the theories and programs to determine their effectiveness. The authors and publisher make no warranty of any kind, expressed or implied, with regard to these programs or to the documentation contained in these books. The authors and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs.