How to return a list on the end of a recursive function in Python

Question

I was playing with the fibonacci sequence in Python (I know the implementation with yield, but wanted to implement it with recursion) and ended up with the following code snippet:

def fib(start, leng):
    """ Recursive Fibbo"""
    # Should be lists
    if type(start) == int:
        start = [start]

    # Escape route
    if len(start) == leng:
        print start
        return start

    # Run
    else:
        if int(start[-1]) == 0:
            start.append(1)
        else:
            if len(start) == 1:
                start.append(start[-1])

        next_number = int(start[-1]) + int(start[-2])
        start.append(next_number)
        fib(start, leng)

Now, it works like this:

>>> a = fib(0, 10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>> type(a)
<type 'NoneType'>
>>> 

It calculates the sequence, and in the end print it... But... How I could do to it return the list as well?

Is it possible to do without any other helper function nor using yield not any external lib?

If not, why? (and if yes, how)?

Thanks! :)

Answer 1

Just change the last line to

 return fib(start,  leng)

This will go down the line of the recursion to do the "next bit" of work and return the final product that is based on your base case defined earlier in your code as your escape route:

# Escape route
if len(start) == leng:
    print start
    return start

Once you hit the return in your escape route, the return gets propagated back up the call stack, each call to return fib(start, leng) returning up to itself the complete answer. Once the call stack is back in your original call to the function (made elsewhere), the function actually completes and returns your expected value.

Answer 2

Your last line also needs to be a return:

return fib(start, leng)

Without that, your return value from the "escape route" is not propagated back.