SolarPixelGaming - 1 year ago 71

Python Question

Okay, this question is a little strange, but I was wondering if I could do it like this.

I'm working on a simple Fibonacci number generator for fun since I was interested in programming it.

So I wrote this out:

`def f(n):`

if n == 1: return 1

if n == 2: return 2

else:

return f(n-1) + f(n-2)

and that ran very slowly, taking 15 seconds to do

`f(30)`

So then I wrote this:

`def f(n):`

global a

if n == 1: return 1

if n == 2: return 1

else:

if "fib(%s)" % n in a:

return a["fib(%s)" % n]

else:

z = f(n-1) + f(n-2)

a["fib(%s)" % n] = z

return z

which basically stores previous results in a dictionary like so:

`{'f(1)':1,'f(2)':2,'f(3)':3,'f(4)':5}`

This made it tons faster. I could do

`f(100)`

`f(4000)`

So I added

`a = {}`

`a`

So doing this:

`def f(n):`

global a

if n == 1: return 1

if n == 2: return 1

else:

if "fib(%s)" % n in a:

return a["fib(%s)" % n]

else:

z = f(n-1) + f(n-2)

a["fib(%s)" % n] = z

return z

a = {}

didn't work. but if I do this:

`def f(n):`

global a

if n == 1: return 1

if n == 2: return 1

else:

if "fib(%s)" % n in a:

return a["fib(%s)" % n]

else:

z = f(n-1) + f(n-2)

a["fib(%s)" % n] = z

return z

# now run the function

f(100)

a = {}

`a`

Answer Source

Your `a = {}`

statement inside the function was never being executed; every possible path of execution reaches a `return`

before then. If it WAS executed, you wouldn't have liked the results - it would have executed in every single recursive call to the function, meaning that your dictionary would never hold more than one item! You would somehow have to detect the outermost call and only clear the dict there, or (much simpler) clear it outside of the recursion as in your second example.

Note that much of the size of your dictionary is coming from the strange decision to use a long string key. Keying it with the number itself (as in `a[n] = z`

) would make it much more compact.

(For future reference: the technique you've come up with here, of saving the results from previous function calls, is known as "memoization".)