Counting recursive calls

Dev Shed Forums Sponsor:

May 23rd, 2013, 03:25 AM

SimonWr

Registered User

Join Date: May 2013

Posts: 6

Time spent in forums: 2 h 10 m 24 sec
Reputation Power: 0

Counting recursive calls

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).

May 23rd, 2013, 04:54 AM

Mekire

Contributing User

Join Date: Oct 2012

Posts: 170

Time spent in forums: 3 Days 7 h 47 m 5 sec
Reputation Power: 2

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:

python Code:

Original - python Code
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)))

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

Comments on this post

Nyktos agrees!

May 23rd, 2013, 07:18 AM

Nyktos

Contributing User

Join Date: Dec 2012

Posts: 114

Time spent in forums: 1 Day 11 h 54 m 6 sec
Reputation Power: 3

This one only works in Python 3:

Code:

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

May 23rd, 2013, 10:50 AM

SimonWr

Registered User

Join Date: May 2013

Posts: 6

Time spent in forums: 2 h 10 m 24 sec
Reputation Power: 0

Thanks Again Mek

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

Code:

if __name__ == "__main__":

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

Quote:

Originally Posted by Mekire

python Code:

Original - python Code
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)))

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

May 23rd, 2013, 10:58 AM

Mekire

Contributing User

Join Date: Oct 2012

Posts: 170

Time spent in forums: 3 Days 7 h 47 m 5 sec
Reputation Power: 2

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:

python Code:

Original - python Code
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)))

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)))

Last edited by Mekire : May 23rd, 2013 at 11:15 AM.

May 23rd, 2013, 02:48 PM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 4,124

Time spent in forums: 1 Month 3 Weeks 2 Days 4 h 37 m 27 sec
Reputation Power: 455

Please ignore this bad posting.

[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

Code:

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'

__________________
[code]Code tags[/code] are essential for python code!

Last edited by b49P23TIvg : May 25th, 2013 at 08:28 PM. Reason: This post sucks big time.

May 23rd, 2013, 09:47 PM

Mekire

Contributing User

Join Date: Oct 2012

Posts: 170

Time spent in forums: 3 Days 7 h 47 m 5 sec
Reputation Power: 2

Quote:

Code:

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:

Code:

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]

Last edited by Mekire : May 23rd, 2013 at 10:44 PM.

May 23rd, 2013, 10:40 PM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 4,124

Time spent in forums: 1 Month 3 Weeks 2 Days 4 h 37 m 27 sec
Reputation Power: 455

I had a bad day at the forums!

May 24th, 2013, 10:32 PM

zxq9

Contributing User

Join Date: May 2013

Location: Usually Japan when not on contract

Posts: 240

Time spent in forums: 2 Days 11 h 54 m
Reputation Power: 11

Don't use variables

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.

python Code:

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

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:

Code:

>>> 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().

#10

May 25th, 2013, 12:02 AM

Mekire

Contributing User

Join Date: Oct 2012

Posts: 170

Time spent in forums: 3 Days 7 h 47 m 5 sec
Reputation Power: 2

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

-Mek

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

python Code:

Original - python Code
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)))

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:

Code:

>>> 
- 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

Comments on this post

b49P23TIvg agrees: I retracted my post 6. Thank you.

Last edited by Mekire : May 25th, 2013 at 12:40 AM.

#11

May 25th, 2013, 02:34 AM

zxq9

Contributing User

Join Date: May 2013

Location: Usually Japan when not on contract

Posts: 240

Time spent in forums: 2 Days 11 h 54 m
Reputation Power: 11

Quote:

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.

python Code:

Original - python Code
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)

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)

Code:

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

Counting recursive calls

Developer Shed Advertisers and Affiliates