Question

Using Python, create program to count number of recursive steps for Fibonacci(30) and just submit the number.

Answer 1

By using a global variable outside the function, and updating each time the function is called will give the number of recursive steps it takes to get the output:

Python code:

# Function for nth Fibonacci number
def Fibonacci(n):
global count
if n<0:
count = count+1
print("Incorrect input")
# First Fibonacci number is 0
elif n==1:
count = count+1
return 0
# Second Fibonacci number is 1
elif n==2:
count = count+1
return 1
else:
count = count+1
return Fibonacci(n-1)+Fibonacci(n-2)

# Driver Program
count =0
print("30th number of Fibonacci series: ",Fibonacci(30))
print("Number of Steps: ",count)

Output:

Python 3.6.1 (default, Dec 2015, 13:05:11) [GCC 4.8.2] on 1linux 30th number of Fibonacci series: 514229 Number of Steps: 1664079

# Function for nth Fibonacci number def Fibonacci(n): global count if n<e: count count+1 print( Incorrect input") # First Fibonacci number is elif n=-1: countcount+1 return 0 # Second Fibonacci number is 1 elif n- 2: count-count+1 return 1 else countcount+1 return Fibonacci(n-1)+Fibonacci (n-2) # Driver Program count0 print("30th number of Fibonacci series ",Fibonacci(3e)) print("Number of Steps ",count)