Question

In the Spring 2013 Edition of this book, on page 50, figure 4.10. This code for the Fibonacci sequence is give.

def fib(x):
"""assumes x an int >= 0 returns Fibonacci of x """
global numCalls
numCalls += 1
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)


def testFib(n):
for i in range(n+1):
global numCalls
numCalls = 0
print 'fib of ', i, '=', fib(i)
print 'fib called', numCalls, 'time.'

Is there an error. Should numCalls = 0 ?

Answer 1

Yes. It needs to be reset every time you test it.

Answer 2

See, they are using a global to keep track of the number of calls for each Fibonacci sequence it generates. Every time it advances, it resets the number of calls so that you see the number of calls for only that particular run.

Answer 3

I don't see what you mean. Wouldn't it make more sense to move the global numCall out of both functions entirely and just keep numCall +=1 in each function. Then it'll count how many times it calls the variable for each function.

Answer 4

You would still need to reset it inside the test function. They don't seem to want the grand total for all sequences. Just a total for one sequence at a time.

Answer 5

So it's correct when numCalls always comes up as 1. If I had this function run twice, within a larger function then numCalls should come up as 2?

Answer 6

It would come up as different values depending on the size of the tested range.

Answer 7

do testFib(5)

Answer 8

fib(5) = 8, when I print numCalls it comes up as 1, which is what it comes up as when I run testFib

Answer 9

```
def fib(x):
"""assumes x an int >= 0 returns Fibonacci of x """
global numCalls
numCalls += 1
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)

def testFib(n):
for i in range(n+1):
global numCalls
numCalls = 0
print 'fib of ', i, '=', fib(i)
print 'fib called', numCalls, 'time.'

testFib(5)
```
gets me:

```
*** Python 2.7.6 (default, Nov 10 2013, 19:24:24) [MSC v.1500 64 bit (AMD64)] on win32. ***
*** Remote Python engine is active ***
>>>
*** Remote Interpreter Reinitialized ***
>>>
fib of 0 = 1
fib called 1 time.
fib of 1 = 1
fib called 1 time.
fib of 2 = 2
fib called 3 time.
fib of 3 = 3
fib called 5 time.
fib of 4 = 5
fib called 9 time.
fib of 5 = 8
fib called 15 time.
>>>
```

Answer 10

See now that makes sense, but that's not what I'm getting. I get an error when I use the program verbatim from the book.

Answer 11

What version of Python are you using?

Answer 12

2.5.4

Answer 13

Hmmm.... Just ran it on 2.5

Python 2.5.4 (r254:67916, Dec 23 2008, 15:10:54) [MSC v.1310 32 bit (Intel)] on win32

```
def fib(x):
"""assumes x an int >= 0 returns Fibonacci of x """
global numCalls
numCalls += 1
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)

def testFib(n):
totalCalls = 0
for i in range(n+1):
global numCalls
numCalls = 0
print 'fib of ', i, '=', fib(i)
print 'fib called', numCalls, 'time.\n'
totalCalls = totalCalls + numCalls
print "Total of all calls is: ", totalCalls

testFib(5)
```
and got:
```
>>>
fib of 0 = 1
fib called 1 time.

fib of 1 = 1
fib called 1 time.

fib of 2 = 2
fib called 3 time.

fib of 3 = 3
fib called 5 time.

fib of 4 = 5
fib called 9 time.

fib of 5 = 8
fib called 15 time.

Total of all calls is: 34
>>>
```

Answer 14

I think I got it. numCalls = 0 goes in both functions. fib only gives me the number in the sequence and testFib, gives me the fib sequence and the number of times it has been called. I had removed numCalls = 0 from the testFib function. Now I'm getting what you're getting.

Answer 15

That's the error in the book you mentioned?

Answer 16

I do not have numCalls = 0 in both. I see no error.

Answer 17

def fib(x):
"""assumes x an int >= 0 returns Fibonacci of x """
global numCalls
numCalls = 0
numCalls += 1
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)

def testFib(n):
for i in range(n+1):
global numCalls
numCalls = 0
print 'fib of ', i, '=', fib(i)
print 'fib called', numCalls, 'time.'

Answer 18

It only runs def fib(x) when I use numCalls= 0, otherwise I get an error.

Answer 19

With it using a global in the way it is, you can NOT do fib(5) directly. You MUST use it through the test harness or some other method that creates the global properly so that there is not an error.

Answer 20

Some comments as to what happens:
```
def fib(x):
"""assumes x an int >= 0 returns Fibonacci of x """
global numCalls # This line tells it that a global will be used.
numCalls += 1 # This line uses a global, but only works if the global exists.
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)

def testFib(n):
totalCalls = 0
for i in range(n+1):
global numCalls # This line tells it that a global will be used.
numCalls = 0 # This line defines/creates the global.
print 'fib of ', i, '=', fib(i)
print 'fib called', numCalls, 'time.\n'
totalCalls = totalCalls + numCalls
print "Total of all calls is: ", totalCalls
```

Answer 21

You are correct, if I run testFib first and the fib, I get no errors and the correct answer for both, when using the code verbatim from the book.

Answer 22

Gotcha, now it makes sense.
Thanks so much for the help and have a nice day.

Answer 23

It always takes people a little but to get one concept or another. This one is a key one in computing. Fariables must be declared before they canbe used. Python is more forgiving about this, but the rule still applies.

In python:
```
x = 5
print x
````
That works. But in Java:
```
x = 5;
System.out.println(x);
```
would fail because you would need to tell it that x is an integer (number).
```
int x;
x = 5;
System.out.println(x);
```
or:
```
int x = 5;
System.out.println(x);
```
Would be the fix in java. Same basic issue you were having, I would be using it before defining it.

Answer 24

Ooops.... I mised one of the ``` sets so my code blocks are messed up. LOL

Answer 25

No worries, but I see exactly what you mean. For some reason it just never occurred to me to run a program to define or declare a variable. Thanks.

Answer 26

Guntag loves using a test harness for his stuff. I can understand why. It is more like how real world programming is done.

Answer 27

https://en.wikipedia.org/wiki/Test_harness

Answer 28

Given all the nuances that can cause an error, including user error, it makes sense.

Answer 29

Once again thanks for the help and take care.