1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
May 2013
Posts
6
Rep 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).
2. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2012
Posts
194
Rep Power
6
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:
```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 agrees
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2012
Posts
114
Rep Power
7
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```
4. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
May 2013
Posts
6
Rep Power
0

#### Thanks Again Mek

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

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

-Mek
5. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2012
Posts
194
Rep Power
6
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:
```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 10:15 AM.

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'
Last edited by b49P23TIvg; May 25th, 2013 at 07:28 PM. Reason: This post sucks big time.
7. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2012
Posts
194
Rep Power
6
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 09:44 PM.
9. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
May 2013
Location
Usually Japan when not on contract
Posts
240
Rep Power
16

#### 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:
```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. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Oct 2012
Posts
194
Rep Power
6
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:
```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```

• b49P23TIvg agrees : I retracted my post 6. Thank you.
Last edited by Mekire; May 24th, 2013 at 11:40 PM.
11. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
May 2013
Location
Usually Japan when not on contract
Posts
240
Rep Power
16
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:
```def fib(x, depth=0):
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
Depth of current call:  1
Depth of current call:  2
Depth of current call:  3
Depth of current call:  4
Depth of current call:  5
Depth of current call:  5
Depth of current call:  4
Depth of current call:  3
Depth of current call:  4
Depth of current call:  4
Depth of current call:  2
Depth of current call:  3
Depth of current call:  4
Depth of current call:  4
Depth of current call:  3
Depth of current call:  1
Depth of current call:  2
Depth of current call:  3