Python: clean up my list for reuse (fibonacci example)

Question

So I’m trying to show that the recursive method to produce a fibonacci number is very inefficient, I'm using a list cause they are called by reference and therefore once the functions split up they still change the same variable. The Problem: i don't know how to clean up the list when we're done. Which leads to the problem that at the first run through our list goes through 1 to 5 which is desired, but starts on the 2nd run through from 6 to 10.

# Iterative method has exactly n repetitions
# let's compare recursive method:
def fiborec(n, i = []):
    i.append(len(i)+1)
    print('this is call nr.:', len(i))

    if n == 0:
        return 0
    elif(n == 1):
        return 1
    else:
        return fiborec(n - 1, i) + fiborec(n - 2, i)

I also tried:

def fiborec(n, i = [0]):
    i[0] += 1
    print('this is call nr.:', i[0])

Both methods show the same behaviour :( this leads me to expect that, i = [0] is not used because a reference already exists.

del i[:] won't work because there's no definite end since we have two ending conditions, so the place where to add it is somewhat unclear - to me at least.

So... my temporary fix:

def fiborec(n):
    """Docstring: returns Fibonacci Number for given Int. 

recursive method

"""
    i = [0] # we want i to be "passed by reference" due to lots of function calls
            # but also to be resetted should we reuse the function
    return _fiborecursion(n, i)

I don't like it but it's the best I can think of right now D: Should anyone have a solution where I don't need two functions please let us know ^_^

Use `i=None` as the default, then check `if i is None: i = []` when the function is first called. That's the typical way to avoid this issue (http://stackoverflow.com/q/1132941/3001761). Or implement memoization as a decorator. — jonrsharpe, Nov 13 '15 at 13:21
well, i have now decide to create a function that runs once just to reset the counter and then calls the recursive function... not pretty in my eyes but the best i could think of. I'll be sure to read through the link though. TY — Andreas, Nov 16 '15 at 10:45

score 1 · Answer 1 · answered May 15 '16 at 22:42

I believe @jonrsharpe's suggestion will fix your original problem:

def fiborec(n, i=None):
    if i is None:
        i = [1]
    else:
        i.append(len(i) + 1)
    print('this is call nr.:', i[-1])

    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fiborec(n - 1, i) + fiborec(n - 2, i)

Generating for fiborec(10):

('this is call nr.:', 1)
('this is call nr.:', 2)
('this is call nr.:', 3)
('this is call nr.:', 4)
('this is call nr.:', 5)
...
('this is call nr.:', 173)
('this is call nr.:', 174)
('this is call nr.:', 175)
('this is call nr.:', 176)
('this is call nr.:', 177)
55

But can be called again (sans second argument) without side effect.

However, if you are indeed:

trying to show that the recursive method to produce a fibonacci number is very inefficient

play fair and use an efficient recursive fibonacci solution:

def fibofast(n, res=0, nxt=1, i=None):
    if i is None:
        i = [1]
    else:
        i.append(len(i) + 1)
    print('this is call nr.:', i[-1])

    if n == 0:
        return res
    return fibofast(n - 1, nxt, res + nxt, i)

Generating for fibofast(10):

('this is call nr.:', 1)
('this is call nr.:', 2)
('this is call nr.:', 3)
('this is call nr.:', 4)
('this is call nr.:', 5)
('this is call nr.:', 6)
('this is call nr.:', 7)
('this is call nr.:', 8)
('this is call nr.:', 9)
('this is call nr.:', 10)
('this is call nr.:', 11)
55

Python: clean up my list for reuse (fibonacci example)

1 Answers1