[SimonWr]

Having read how to use global variables to count recursive calls, I want to count calls in function without using global variable. My best attempt follows (it Fails!)


numOfCalls = 1
def fib(x, numOfCalls):
"""
assumes x an integer > 0
returns fibonacci of x
"""



print 'number of calls is ',numOfCalls
if x == 0 or x == 1:
return 1

else:
return fib(x-1, numOfCalls + 1) + fib(x-2, numOfCalls + 2)




fib(5, numOfCalls)


Any help would be appreciated
My attempt does generate 15 print lines, I would therefore like to count the print lines but not sure how to do this.
I would also appreciate to know where I can read up how to format code to present on this forum (I am pasting from IDLE).

[Mekire]

Use the # button in the tool bar for code tags. After pasting your code, highlight it and hit that button.

Anyway, this is of course trivial if you use a class with an identical method to using a global, except with a class attribute instead.

With just a function however it is a bit tricky. This seems to do the trick:

def fib(x,num_calls=0):
    """
    assumes x an integer > 0
    returns fibonacci of x
    """
    if x == 0 or x == 1:
        return 1,num_calls+1
 
    else:
        a,num_calls = fib(x-1,num_calls)
        b,num_calls = fib(x-2,num_calls)
        return a+b,num_calls+1
 
if __name__ == "__main__":
    x = 5
    print("Fib({}) = {}\nCalls = {}".format(x,*fib(x)))

-Mek

[Nyktos]

This one only works in Python 3:

def fib(x):
    num_calls = 0
    def _fib(x):
        nonlocal num_calls
        num_calls += 1
        if x in {0, 1}:
            return 1
        else:
            return _fib(x - 2) + _fib(x - 1)
    return _fib(x), num_calls

[SimonWr]

Thanks Mek
your function works well.
There are a few new concepts in code that I need to explore!
What does this do?

if __name__ == "__main__":

I am hoping last line delivers as code tags
If it does thanks also for teaching me this
Simon

Originally Posted by Mekire

Use the # button in the tool bar for code tags. After pasting your code, highlight it and hit that button.

Anyway, this is of course trivial if you use a class with an identical method to using a global, except with a class attribute instead.

With just a function however it is a bit tricky. This seems to do the trick:

def fib(x,num_calls=0):
    """
    assumes x an integer > 0
    returns fibonacci of x
    """
    if x == 0 or x == 1:
        return 1,num_calls+1
 
    else:
        a,num_calls = fib(x-1,num_calls)
        b,num_calls = fib(x-2,num_calls)
        return a+b,num_calls+1
 
if __name__ == "__main__":
    x = 5
    print("Fib({}) = {}\nCalls = {}".format(x,*fib(x)))

-Mek

[Mekire]

That lines tells the interpreter to only execute the code in that block if the program is run as main. If you import it from another module it won't run that. This way if you wanted to import and use your fib function in another file you wouldn't have to worry about that file printing our fib(5) calculation. Basically no real python program executes any code (save for imports and perhaps global assignments) in the raw global namespace. This is a good habit to get into early as you will see it a lot.

I would also like to note that recursively calculating Fibonacci numbers like this is stupendously inefficient. This excercise only serves to teach you how to use recursion; it does nothing to teach you when to use it.

-Mek

Edit:
Here is a non-recursive version if you are interested that uses a generator:

import sys
if sys.version_info[0] == 2: range = xrange #version compatibility
 
def fib_gen():
    a = 0; b = 1
    while 1:
        a,b = b,a+b
        yield a
 
if __name__ == "__main__":
    fibby = fib_gen()
    for i in range(100):
        print("Fibbonacci #{:<4} : {}".format(i+1,next(fibby)))

[b49P23TIvg]

[edit]Mekire proved this post is wrong. Please ignore it.[/edit]


Two other ways to count recursive calls without using a global.

Use a class, update the counter in the object.

and

def recursive(args, count_in_item_0_of_this_list):
    count_in_item_0_of_this_list[0] += 1
    #...

counter = [0]
result = recursive(args, counter)
print('calls:', counter[0])

It would make a nice decorator.



Thank you for example of nonlocal . I hadn't known of a use for it.



When you invoke python the module name is
'__main__'

And that's why the __name__ test causes different behavior in

$ python myprogram.py

versus

$ python -c 'import myprogram'

[Mekire]

def recursive(args, count_in_item_0_of_this_list):
    count_in_item_0_of_this_list[0] += 1
    #...

counter = [0]
result = recursive(args, counter)
print('calls:', counter[0])

You are passing it in as an argument, but this is still tantamount to modifying a global variable; wouldn't you say? The end result is that a global has been modified. The use of a mutable data type is just masking this fact.

Also I mentioned the using a class attribute in my first post

-Mek

Edit: I suppose you could wrap it up just as the nonlocal version did:

def fib(x):
    num_calls = [0]
    def _fib(x):
        num_calls[0] += 1
        if x in {0, 1}:
            return 1
        else:
            return _fib(x - 2) + _fib(x - 1)
    return _fib(x), num_calls[0]

[b49P23TIvg]

I had a bad day at the forums!

[zxq9]

Some of the responses up there are swimming very hard against the current to make Python (and recursive calls) work in a way that isn't natural.

All you need is an accumulator argument. It is a function argument that passes an idea of state along with it, so the function wraps state bits without accessing (or screwing up) any global values. In strict functional languages this is one method of passing state along since in those languages variables are either not permitted to exist or are illegal to change.

def countdown(x, depth=0):
    if x > 0:
        print x
        countdown(x - 1, depth + 1)
    else:
        print "Blastoff!"
        print "Depth of recursion was: ", depth

That's all there is to it:

>>> countdown(10)
10
9
8
7
6
5
4
3
2
1
Blastoff!
Depth of recursion was:  10

This may not seem very special at first, until you consider safety in a parallel processing environment. It has only one side effect: the effect of calling print().

[Mekire]

Recursive depth and number of function calls are NOT the same thing.

-Mek

Edit: Showing depth and call count for the OPs fib(5):

def fib(x):
    calls = [0]
    def _fib(x,depth=0):
        calls[0] += 1
        depth += 1
        print("{} Depth: {}, Calls: {}".format("-"*depth,depth,calls[0]))
        if x in (0,1):
            print("{} Returning 1".format("-"*depth))
            return 1
 
        else:
            print("{} Returning fib({})-fib({})".format("-"*depth,x-1,x-2))
            return _fib(x-1,depth) + _fib(x-2,depth)
    return _fib(x)
 
if __name__ == "__main__":
    x = 5
    print("\nFib {}: {}".format(x,fib(x)))

Output:

>>> 
- Depth: 1, Calls: 1
- Returning fib(4)-fib(3)
-- Depth: 2, Calls: 2
-- Returning fib(3)-fib(2)
--- Depth: 3, Calls: 3
--- Returning fib(2)-fib(1)
---- Depth: 4, Calls: 4
---- Returning fib(1)-fib(0)
----- Depth: 5, Calls: 5
----- Returning 1
----- Depth: 5, Calls: 6
----- Returning 1
---- Depth: 4, Calls: 7
---- Returning 1
--- Depth: 3, Calls: 8
--- Returning fib(1)-fib(0)
---- Depth: 4, Calls: 9
---- Returning 1
---- Depth: 4, Calls: 10
---- Returning 1
-- Depth: 2, Calls: 11
-- Returning fib(2)-fib(1)
--- Depth: 3, Calls: 12
--- Returning fib(1)-fib(0)
---- Depth: 4, Calls: 13
---- Returning 1
---- Depth: 4, Calls: 14
---- Returning 1
--- Depth: 3, Calls: 15
--- Returning 1

Fib 5: 8

[zxq9]

Originally Posted by Mekire

Recursive depth and number of function calls are NOT the same thing.

Indeed they are not.

And maintaining global state is a Bad Thing when writing recursive functions -- which is why accumulators have been used since the before the word "functional" referred to a style of programming. This is true even if that global state isn't global to anything other than concurrent executions of the recursive function, because you can never know whether they are executing in a sequential stack (the way CPython implements it) or are actually represent concurrent tail recursive branches executing in parallel (like in Iron Python) or even don't get executed at all because of a memoization optimizer operating in the background.

def fib(x, depth=0):
   print "Received x: ", x
   print "Depth of current call: ", depth
   if x == 0:
     return x
   elif x == 1:
     return x
   else:
     return fib(x - 1, depth + 1) + fib(x - 2, depth + 1)
 
print fib(6)

Received x:  6
Depth of current call:  0
Received x:  5
Depth of current call:  1
Received x:  4
Depth of current call:  2
Received x:  3
Depth of current call:  3
Received x:  2
Depth of current call:  4
Received x:  1
Depth of current call:  5
Received x:  0
Depth of current call:  5
Received x:  1
Depth of current call:  4
Received x:  2
Depth of current call:  3
Received x:  1
Depth of current call:  4
Received x:  0
Depth of current call:  4
Received x:  3
Depth of current call:  2
Received x:  2
Depth of current call:  3
Received x:  1
Depth of current call:  4
Received x:  0
Depth of current call:  4
Received x:  1
Depth of current call:  3
Received x:  4
Depth of current call:  1
Received x:  3
Depth of current call:  2
Received x:  2
Depth of current call:  3
Received x:  1
Depth of current call:  4
Received x:  0
Depth of current call:  4
Received x:  1
Depth of current call:  3
Received x:  2
Depth of current call:  2
Received x:  1
Depth of current call:  3
Received x:  0
Depth of current call:  3
8