Authors:
Y Daniel Lang
Chapter:
5.recursion
Exercise:
Programming Excercises
Question:2 | ISBN:978013274719 | Edition: 6
Question
(Fibonacci numbers) Rewrite the fib function in Listing 15.2 using iterations.
(Hint: To compute fib(n) without recursion, you need to obtain fib(n - 2) and fib(n - 1) first.) Let f0 and f1 denote the two previous Fibonacci umbers.
The current Fibonacci number would then be f0 + f1. The algorithm can be described as follows:
f0 = 0 # For fibs(0)
f1 = 1 # For fib(1)
for i in range(2, n + 1):
currentFib = f0 + f1
f0 = f1
f1 = currentFib
# After the loop, currentFib is fib(n)
Write a test program that prompts the user to enter an index and displays its Fibonacci number.
Answer
A test program that prompts the user to enter an index and displays its Fibonacci number:
CODE:
def fibonacci(n): #defining fibonacci function
f0 = 0 # assining value of fib(0) to f0
f1 = 1 # assining value of fib(1) to f1
if n < 0: #check whether given index is non zero
print("Incorrect input") # if yes, display incorrect input
elif n == 0: # if n=0, diplay 0
return f0
elif n == 1: #if n=1,display1
return f1
else: #else follow the loop
for i in range(2, n):
currentFib = f0 + f1
f0 = f1
f1 = currentFib
return f1
num = int(input("Enter an index:"))
print(fibonacci(num)) # display febonacci number
OUTPUT:
Enter an index:9
21
Enter an index:1
1
Enter an index:0
0