Intuition behind tail recursionin Fibonacci-CodePudding

The following code compute the nth Fibonnacci number:

def fib(n, a=0, b=1):
    return fib(n-1, b, a b) if n > 0 else a

I am struggling to understand how to come up with such a solution. It looks like the formula comes from a void. However, there must be some steps that led so such a formula. Unfortunately, such a scaffolding has been removed and a clean formula is given.

PS: I am aware that Python does not have TCO.

If there is some graph or animation, it would be perfect.

CodePudding user response：

So. The best explanation I can come up with. Normally, Fibonacci numbers start with 0, 1, to give the sequence

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

But you can have sequences that start with any pair of numbers. For example

2, 5, 7, 12, 19, 31, 50, ....

Now here's an interesting fact. Look at the sequence

1, 1, 2, 3, 5, 8, 13, 21, ...

it's one of these alternative sequences, but it starts with 1, 1. And it just happens to be the elements of the Fibonacci sequence missing the first one. And

1, 2, 3, 5, 8, 13, 21, 34, ...

is another of these alternate sequences, but it's also the Fibonacci sequence missing the first two elements.

So fib(n, a, b) is just "give me the nth element of the 'alternative' Fibonacci sequence whose first two elements are a and b.

CodePudding user response：

n is the reversed index of fib values

a is fib(n) beginning at 0

b is fib(n 1)

CodePudding user response：

As n decreases with every recursive call, b is passed as the new a while the new b is the old a b. Notice how that represents exactly the fibonacci logic:

n  0 1 1 2 3 5 8 
5  a b
4    a b
3      a b
2        a b
1          a b
0            a b  # -> fib(5) == 5 (== a)

CodePudding user response：

Trace through the calls, for n=5 in this case:

def fib(n, a=0, b=1):
    return fib(n-1, b, a b) if n > 0 else a

call fib(5)
    call fib(4, 1, 1)
        call fib(3, 1, 2)
            call fib(2, 2, 3)
                call fib(1, 3, 5)
                    call fib(0, 5, 8)
                        return 5
                    return 5
                return 5
            return 5
        return 5
    return 5

CodePudding user response：

this is basically the iterative version but written in recursive form:

def fibi(n,a=0,b=1):
    while n>0:
        a,b = b, a b
        n = n-1
    return a

in both cases n is no more that a counter that tell us how many times we should do the a,b = b, a b step, is the same if we initialize a counter i=0 and count up to until we get to n or like here we decrease n which in this case tell us how many step we have left

CodePudding user response：

The code seems to be just a fancy way of rewriting a simple loop.

Note that n in the recursive code does not interact at all with a or b. It serves just as a counter. It decreases by 1 each time, and when it becomes 0, recursion ends. So it really is just a for loop with n iterations. Then the way a and b are switched everytime, which is fairly a standard way of calculating Fibonacci.

So the following is more or less equivalent rewriting of the code:

def fib(n):
    a = 0
    b = 1
    for _ in range(n):
        a, b = b, a   b
    return a