10 Replies - 3778 Views - Last Post: 15 October 2012 - 07:46 PM Rate Topic: -----

#1 q81101  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 28-September 12

How to find out the recursive calls for fibonacci?

Posted 14 October 2012 - 01:44 AM

def main():
    index = eval(input("Enter an index for a fibonacci number: "))
    # Find and display the Fibonacci number
    print("The Fibonacci number at index", index, "is", fib(index))
    

# The function for finding the Fibonacci number
def fib(index):
    if index == 0:
        return 0
    elif index == 1:
        return 1
    else:
        return fib(index - 1) + fib(index - 2)


        

main()


How can I finds the number of times the fib function is called.

number of time fib is call in fib(0) = 1
number of time fib is call in fib(1) = 1
then everytime the number of time fib is call will be
1 + two previous fib number of calls.

I know the logic but I don't know how to write the code.

Is This A Good Question/Topic? 0
  • +

Replies To: How to find out the recursive calls for fibonacci?

#2 darek9576  Icon User is offline

  • D.I.C Lover

Reputation: 198
  • View blog
  • Posts: 1,689
  • Joined: 13-March 10

Re: How to find out the recursive calls for fibonacci?

Posted 14 October 2012 - 05:59 AM

you could create some variable and increment it inside the fib function.
Was This Post Helpful? 2
  • +
  • -

#3 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: How to find out the recursive calls for fibonacci?

Posted 14 October 2012 - 07:24 AM

There are basically two approaches you can use. The first, and simplest is creating a global variable called calls and incrementing that. This variable would have to be created outside the fib function, otherwise it would be re-created on each recursive call.

However, globals make me sad.

The second approach is slightly more difficult, but I believe it's the better way to go. In this approach, you would simply make the fib function return two values in every circumstance, 1 value for the fib numbers, 1 value for the count. Basically, it'll be like keeping track of two fibs instead of 1. I have a working solution in the spoiler tags.
Spoiler

Was This Post Helpful? 1
  • +
  • -

#4 q81101  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 28-September 12

Re: How to find out the recursive calls for fibonacci?

Posted 14 October 2012 - 11:58 AM

Can any of you provide the example of global variable???
Was This Post Helpful? 0
  • +
  • -

#5 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: How to find out the recursive calls for fibonacci?

Posted 14 October 2012 - 07:33 PM

hmmm, I keep trying, but it keeps coming out wrong... the more I try to fix it the further off the answers get! I just can't seem to bring myself to use them.

On a more serious/useful note, global variables are typically frowned upon by most programmers, so I don't experience programmers don't tend to use them very much.

On a side note, it's important to check standard cases when you create code. Your fib works well for 0 and for positive numbers... but did you ever try putting in a negative?

Here's a sorta global version, but it's not really global because everything is still encapsulated in functions:
def fib(index):
    global calls
    calls = 0
    def sub_fib(index):
        global calls
        if index <= 1:
            calls +=1
            return index
        else:
            return sub_fib(index - 1) + sub_fib(index - 2)
    return sub_fib(index), calls           



calls does not need to be declared outside of fib, so it's not really global.

This post has been edited by atraub: 14 October 2012 - 08:03 PM

Was This Post Helpful? 1
  • +
  • -

#6 q81101  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 28-September 12

Re: How to find out the recursive calls for fibonacci?

Posted 14 October 2012 - 08:13 PM

Just somethin not right
def main():
    index = eval(input("Enter an index for a fibonacci number: "))
    # Find and display the Fibonacci number
    print("The Fibonacci number at index", index, "is", fib(index))
    print("The number of time fib calls is", fibCalls(index))
    

# The function for finding the Fibonacci number
def fib(index):
    if index == 0:
        return 0
    elif index == 1:
        return 1
    else:
        return fib(index - 1) + fib(index - 2)
    

calls = 0
def fibCalls(index):
        global calls
        if index <= 1:
            calls += 1
            return index
        else:
            return 1 + fibCalls(index - 1) + fibCalls(index - 2)
    
        
main()


Somehow it's work, but the time calls is wrong.

Ex:
Fib(10)
the time call is 143(wrong), instead of 177.

This post has been edited by atraub: 14 October 2012 - 08:32 PM
Reason for edit:: Removed unnecessary quote

Was This Post Helpful? 0
  • +
  • -

#7 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: How to find out the recursive calls for fibonacci?

Posted 14 October 2012 - 08:32 PM

In both versions of my code, the resulting value is 89 rather than 143 or 177.

EDIT:
You're incrementing calls on both lines 22 and 25, that's probably why yours is much higher than mine. Are you sure the output value should be 177?

This post has been edited by atraub: 14 October 2012 - 08:35 PM

Was This Post Helpful? 0
  • +
  • -

#8 q81101  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 28
  • Joined: 28-September 12

Re: How to find out the recursive calls for fibonacci?

Posted 15 October 2012 - 12:33 AM

View Postatraub, on 14 October 2012 - 08:32 PM, said:

In both versions of my code, the resulting value is 89 rather than 143 or 177.

EDIT:
You're incrementing calls on both lines 22 and 25, that's probably why yours is much higher than mine. Are you sure the output value should be 177?



According to my textbook, the number of call in fib(10) is 177.
Was This Post Helpful? 0
  • +
  • -

#9 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2115
  • View blog
  • Posts: 3,240
  • Joined: 21-June 11

Re: How to find out the recursive calls for fibonacci?

Posted 15 October 2012 - 01:36 AM

View Postatraub, on 15 October 2012 - 04:33 AM, said:

calls does not need to be declared outside of fib, so it's not really global.


More importantly it doesn't need to be reset to 0 outside of fibs if you want to use fibs multiple times and setting it to something else before calling fibs won't change the result.

That said it can still be read globally and if another function also uses a global variable named calls, fibs will happily overwrite it, presumably breaking the other function's functionality. And of course if another function changes calls while fibs is running (say you defined your own output function which keeps track of how often it's called in the same global variable calls, then you forgot that it does that and called it from fibs to debug something), fibs will still break. So it's still at least somewhat global.

In Python 3 you can truly get rid of the global variable by removing line 2 and changing line 5 to nonlocal calls.

PS: To get the correct result using the global/nonlocal variable version, you'd increment the global/nonlocal variable at the beginning of the inner fib function - not inside an if.

@OP: To get the result without calculating the Fibonacci number at the same time, you don't need the calls variable at all (note that you're not actually using the calls variable anywhere in your code - just incrementing it). Your problem is that using your code fibcalls(0) is 0; it should be 1. If you fix that, your code will work and you can remove any reference to the calls variable.

PPS: Another way to keep track of the number of calls of fib while calculating it without using global variables, would be to use an object. So the fib function would create a Fib object and then call .fib(n) on that object. The Fib class would have a calls variable that's initialized to 0 and a fib method that increments that variable while it calculates the Fibonacci number. By making the Fib class local to the fib function and not returning the Fib object, you make sure that the user will not use the fib method twice on the same object, which would break because calls would not be reset.

This post has been edited by sepp2k: 15 October 2012 - 01:49 AM

Was This Post Helpful? 1
  • +
  • -

#10 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5832
  • View blog
  • Posts: 12,684
  • Joined: 16-October 07

Re: How to find out the recursive calls for fibonacci?

Posted 15 October 2012 - 06:25 AM

This looked like fun. I played with this a couple of ways.

def fibCount(base):
	def fib(n, counter):
		counter[0] += 1
		if n in (0,1):
			return n
		return fib(n - 1, counter) + fib(n - 2, counter)
	counter = [0]
	value = fib(base, counter)
	return value, counter[0]


def fibCountSuper(n, cache={0:(0,1),1:(1,1)}):
	if n not in cache:
		v = fibCountSuper(n-2, cache), fibCountSuper(n-1, cache)
		cache[n] = v[0][0] + v[1][0], v[0][1] + v[1][1]
	return cache[n]

def showFib(n, fib):
	value, calls = fib(n)
	print("fib({0}) = {1} : {2} calls made".format(n, value, calls))


def showFibRange(start, stop, fib):
	print(fib.__name__)
	for n in range(start, stop+1):
		showFib(n, fib)
	print('\n')

showFibRange(1, 10, fibCount)
showFibRange(1, 10, fibCountSuper)



Result:
fibCount
fib(1) = 1 : 1 calls made
fib(2) = 1 : 3 calls made
fib(3) = 2 : 5 calls made
fib(4) = 3 : 9 calls made
fib(5) = 5 : 15 calls made
fib(6) = 8 : 25 calls made
fib(7) = 13 : 41 calls made
fib(8) = 21 : 67 calls made
fib(9) = 34 : 109 calls made
fib(10) = 55 : 177 calls made


fibCountSuper
fib(1) = 1 : 1 calls made
fib(2) = 1 : 2 calls made
fib(3) = 2 : 3 calls made
fib(4) = 3 : 5 calls made
fib(5) = 5 : 8 calls made
fib(6) = 8 : 13 calls made
fib(7) = 13 : 21 calls made
fib(8) = 21 : 34 calls made
fib(9) = 34 : 55 calls made
fib(10) = 55 : 89 calls made



The fibCountSuper has the 89 because I screwed up counting self. If, instead, we do:
cache[n] = v[0][0] + v[1][0], v[0][1] + v[1][1] + 1


We'll get 177 for 10.

Note, fibCountSuper is something called memotized. The count given is an artifice. The real count is:
def fibCountSmart(base, cache={0:0,1:1}):
	def fib(n, counter):
		counter[0] += 1
		if n not in cache:
			cache[n] = fib(n-2, counter) + fib(n-1, counter)
		return cache[n]
	counter = [0]
	value = fib(base, counter)
	return value, counter[0]



fibCountSmart
fib(1) = 1 : 1 calls made
fib(2) = 1 : 3 calls made
fib(3) = 2 : 3 calls made
fib(4) = 3 : 3 calls made
fib(5) = 5 : 3 calls made
fib(6) = 8 : 3 calls made
fib(7) = 13 : 3 calls made
fib(8) = 21 : 3 calls made
fib(9) = 34 : 3 calls made
fib(10) = 55 : 3 calls made



Also, I should explain using a list for the counter. Objects! By using the same instance of a list throughout, I can maintain state for all calls. You can't do that with a int, which would be passed by value, not reference. Understanding that you don't get a new copy of a passed list is VERY important in Python.
Was This Post Helpful? 2
  • +
  • -

#11 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 759
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: How to find out the recursive calls for fibonacci?

Posted 15 October 2012 - 07:46 PM

Wow, I gotta admit, I've never seen the nonlocal keyword before, very cool. Admittedly, now that I know that trick (and taking jons other suggestions in), I think this modified version works nicely:
def fib(index):
    calls = 0
    def sub_fib(index):
        nonlocal calls
        calls +=1
        if index <= 1:
            return index
        else:
            return sub_fib(index - 1) + sub_fib(index - 2)
    return sub_fib(index), calls           



This post has been edited by atraub: 15 October 2012 - 07:50 PM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1