Trouble Adding Feature To Recursive Fibonacci Program
Solution 1:
Include the counter inside the function itself and let it return two values (the fibonacci value and the count). This saves you from having to manually do the business logic of resetting the count. You can call the function as many times as you want and the counts will be correct, rather than summing counts from every time ever that fib was called.
def fib(n):
"""Assumes n is int > 0
Returns the nth Fibonacci number and number of times it was called"""
if n == 0 or n == 1:
return n, 0
else:
f1, count1 = fib(n-1)
f2, count2 = fib(n-2)
sum_counts = count1 + count2
if n == 2:
sum_counts = 1
return f1 + f2, sum_counts
def testfib(n):
for i in range(n+1):
f, count = fib(i)
print('fib of', i, 'is ', f, end="\t")
print('count of fib(2) is ', count)
x = int(input('Enter a number: '))
print('Fibonacci of', x, 'is', fib(x)[0])
print(testfib(x))
The output is:
Enter a number: 7
Fibonacci of 7 is 13
fib of 0 is 0 count of fib(2) is 0
fib of 1 is 1 count of fib(2) is 0
fib of 2 is 1 count of fib(2) is 1
fib of 3 is 2 count of fib(2) is 1
fib of 4 is 3 count of fib(2) is 2
fib of 5 is 5 count of fib(2) is 3
fib of 6 is 8 count of fib(2) is 5
fib of 7 is 13 count of fib(2) is 8
None
Since the problem treats the n == 2 case differently, you can make that another base case in your recursion.
def fib(n):
"""Assumes n is int > 0
Returns Fibonacci Number of n and number fo times it was called"""
if n == 0 or n == 1:
return n, 0
elif n == 2:
return (fib(0) + fib(1)), 1
else:
f1, count1 = fib(n-1)
f2, count2 = fib(n-2)
return f1 + f2, count1 + count2
Solution 2:
Function Attributes
This takes advantage of a lesser-known feature of Python established by PEP 232 in order to avoid global variables or creating a full class. Python functions can have their own attributes, which can be used to provide the same functionality as static variables in some other languages. So, in your code you could do something like the following:
def fib(n):
"""Assumes n is int > 0
Returns Fibonacci Number of n"""
if n == 2:
try:
fib.two_count += 1
except AttributeError:
fib.two_count = 1
if n ==0 or n==1:
return n
else:
return fib(n-1) + fib(n-2)
def testfib(n):
for i in range(n+1):
fib.two_count = 0
print(
'fib of', i, 'is ', fib(i),
'and fib(2) was called', fib.two_count, 'times'
)
x=int(input('Enter a number: '))
print('Fibonacci of', x, 'is',fib(x))
print(testfib(x))
Solution 3:
There are neater ways to do this, but the simple way is to use a global variable to keep count of when fib is called with an arg of 2. You need to remember to reset the counter before each outermost call, though.
count = 0
def fib(n):
"""Assumes n is int > 0
Returns Fibonacci Number of n"""
global count
if n == 0 or n == 1:
return n
else:
if n == 2:
count += 1
return fib(n-1) + fib(n-2)
def testfib(n):
global count
for i in range(n+1):
count = 0
print('fib of', i, 'is ', fib(i), ', called fib(2)', count, 'times')
x=int(input('Enter a number: '))
count = 0
print('Fibonacci of', x, 'is', fib(x), ', called fib(2)', count, 'times')
testfib(x)
demo
Enter a number: 7
Fibonacci of 7 is 13 , called fib(2) 8 times
fib of 0 is 0 , called fib(2) 0 times
fib of 1 is 1 , called fib(2) 0 times
fib of 2 is 1 , called fib(2) 1 times
fib of 3 is 2 , called fib(2) 1 times
fib of 4 is 3 , called fib(2) 2 times
fib of 5 is 5 , called fib(2) 3 times
fib of 6 is 8 , called fib(2) 5 times
fib of 7 is 13 , called fib(2) 8 times
A slightly better way is to use a function attribute instead of the modifiable global.
def fib(n):
"""Assumes n is int > 0
Returns Fibonacci Number of n"""
if n == 0 or n == 1:
return n
else:
if n == 2:
fib.count += 1
return fib(n-1) + fib(n-2)
def testfib(n):
for i in range(n+1):
fib.count = 0
print('fib of', i, 'is ', fib(i), ', called fib(2)', fib.count, 'times')
x=int(input('Enter a number: '))
fib.count = 0
print('Fibonacci of', x, 'is', fib(x), ', called fib(2)', fib.count, 'times')
testfib(x)
Solution 4:
You can do it by adding a mutable argument to the function that computes the actual Fibonacci Number—which it will increment each time it's called—and hiding the fact there's now an extra argument with a wrapper function that supplies it:
Here's what I mean:
def dofib(n, count):
"""Assumes n is int >= 0
Returns Fibonacci Number of n."""
count[0] += 1
if n==0 or n==1:
return n
else:
return dofib(n-1, count) + dofib(n-2, count)
def fib(n):
"""Assumes n is int >= 0
Returns Fibonacci Number of n and number of recursive calls."""
count = [0]
return dofib(n, count), count[0]
def testfib(n):
for i in range(n+1):
print('fib of {0} is {1[0]} (call count: {1[1]})'.format(i, fib(i)))
x=int(input('Enter a number: '))
print('Fibonacci of {0} is {1[0]} (call count: {1[1]})'.format(x, fib(x)))
testfib(x)
Sample output:
Fibonacci of 7 is 13 (call count: 41)
fib of 0 is 0 (call count: 1)
fib of 1 is 1 (call count: 1)
fib of 2 is 1 (call count: 3)
fib of 3 is 2 (call count: 5)
fib of 4 is 3 (call count: 9)
fib of 5 is 5 (call count: 15)
fib of 6 is 8 (call count: 25)
fib of 7 is 13 (call count: 41)
Solution 5:
Maybe slightly overkill, but wrapping the entire thing into a class, you can easily introduce a counter. Here you first create a callable Fib object called fib. When you now call fib(x), the counter is set to zero in the __call__ function, which then calls the Fib.fib function which does the actual work. Within the Fib.fib function, the counter is increased by one every time the function argument is equal to 2.
class Fib:
def __init__(self):
self.count = 0
def __call__(self, n):
self.count = 0
return self.fib(n)
def fib(self,n):
"""Assumes n is int > 0
Returns Fibonacci Number of n"""
if n == 2:
self.count += 1
if n ==0 or n==1:
return n
else:
return self.fib(n-1) + self.fib(n-2)
fib = Fib()
x=5
print('Fibonacci of', x, 'is',fib(x))
print('fib(2) was called {} times'.format(fib.count))
For the example argument (x=5), the output is:
Fibonacci of 5 is 5
fib(2) was called 3 times
Post a Comment for "Trouble Adding Feature To Recursive Fibonacci Program"