recursive fibonacci ,stack memory illustration

[mynicks]

I would like to see the progression of the algorithm as it changes values in stack memory (in order to get a better understanding of its internal process in memory). Below is a correct source code that computes the recursive fibonacci.
The question is: how does the algorithm changes values internally in stack memory? Right below i made an attempt to show you the visual model i adopted to understand it.Sadly, i find it difficult to implement my visual model for the fibonacci but it is easy for the factorial !!

#include <cstdio>
#include <cstdlib>
int fib(int n)
{
    int f;
    if(n == 1)
        f = 0;
    else if(n == 2)
        f = 1;
    else
        f =fib(n - 1) + fib(n - 2);
   return f; 

int main(void)
{

    int i ;
    for(i=1;i<11;i++)
        printf("%d\t%d\n",i,fib(i) );
    return EXIT_SUCCESS;
}

To help you understand what i mean here is an example for the factorial.
My stack's memory visual model for the recursive factorial is :

fact(3)--->3*fact(2)--->2*fact(1)--->1 (winding round, aka push)
answer= 6<--- 3* 2 <----2* 1 <---1 (unwinding round, aka pop)

(i do not write the source code for the recursive factorial,google it,it is everywhere)

BUT for the fibonacci sequence how is it gonna look like?? i think the example below is not so correct:
.....................................--f(4)--..........--f(3)--
f(5)-->f(4) + f(3)--->(f(3)+f(2)) + (f(2)+ f(1))--->( (f(2)+f(1)) + 1 ) + (1 +0)
...missing text...confused!

[Sajeel]

can you simply explain what you wanna say and wanna ask

[JLBorges]

#include <iostream>
#include <string>

int fib( int n )
{
    static int depth = 0 ;

    const auto tab = [n]
    { return std::string( depth*4, ' ' ) + " fib(" + std::to_string(n) + ") " ; };

    const auto noisy_ret = [&tab] ( int r )
    { std::cout << tab() << ": return " << r << '\n' ; --depth ; return r ; };

    ++depth ;
    std::cout << tab() << ": begin\n" ;

    if( n < 2 ) return noisy_ret(0) ;
    else if( n == 2 ) return noisy_ret(1) ;
    else
    {
        std::cout << tab() << "== fib(" << n-1 << ") + fib(" << n-2 << ")\n" ;

        std::cout << tab() << ": call fib(" << n-1 << ")\n" ;
        const int fn1 = fib(n-1) ;
        std::cout << tab() << ": fib(" << n-1 << ") returned " << fn1 << '\n' ;

        std::cout << tab() << ": call fib(" << n-2 << ")\n" ;
        const int fn2 = fib(n-2) ;
        std::cout << tab() << ": fib(" << n-2 << ") returned " << fn2 << '\n' ;

        std::cout << tab() << "== fib(" << n-1 << ") + fib(" << n-2 << ") == " << fn1+fn2 << '\n' ;
        return  noisy_ret( fn1+fn2 ) ;
    }
}

int main()
{
    std::cout << "main: call fib(6)\n" ;
    const int f6 = fib(6) ;
    std::cout << "main: fib(6) returned " << f6 << '\n' ;
}

main: call fib(6)
     fib(6) : begin
     fib(6) == fib(5) + fib(4)
     fib(6) : call fib(5)
         fib(5) : begin
         fib(5) == fib(4) + fib(3)
         fib(5) : call fib(4)
             fib(4) : begin
             fib(4) == fib(3) + fib(2)
             fib(4) : call fib(3)
                 fib(3) : begin
                 fib(3) == fib(2) + fib(1)
                 fib(3) : call fib(2)
                     fib(2) : begin
                     fib(2) : return 1
                 fib(3) : fib(2) returned 1
                 fib(3) : call fib(1)
                     fib(1) : begin
                     fib(1) : return 0
                 fib(3) : fib(1) returned 0
                 fib(3) == fib(2) + fib(1) == 1
                 fib(3) : return 1
             fib(4) : fib(3) returned 1
             fib(4) : call fib(2)
                 fib(2) : begin
                 fib(2) : return 1
             fib(4) : fib(2) returned 1
             fib(4) == fib(3) + fib(2) == 2
             fib(4) : return 2
         fib(5) : fib(4) returned 2
         fib(5) : call fib(3)
             fib(3) : begin
             fib(3) == fib(2) + fib(1)
             fib(3) : call fib(2)
                 fib(2) : begin
                 fib(2) : return 1
             fib(3) : fib(2) returned 1
             fib(3) : call fib(1)
                 fib(1) : begin
                 fib(1) : return 0
             fib(3) : fib(1) returned 0
             fib(3) == fib(2) + fib(1) == 1
             fib(3) : return 1
         fib(5) : fib(3) returned 1
         fib(5) == fib(4) + fib(3) == 3
         fib(5) : return 3
     fib(6) : fib(5) returned 3
     fib(6) : call fib(4)
         fib(4) : begin
         fib(4) == fib(3) + fib(2)
         fib(4) : call fib(3)
             fib(3) : begin
             fib(3) == fib(2) + fib(1)
             fib(3) : call fib(2)
                 fib(2) : begin
                 fib(2) : return 1
             fib(3) : fib(2) returned 1
             fib(3) : call fib(1)
                 fib(1) : begin
                 fib(1) : return 0
             fib(3) : fib(1) returned 0
             fib(3) == fib(2) + fib(1) == 1
             fib(3) : return 1
         fib(4) : fib(3) returned 1
         fib(4) : call fib(2)
             fib(2) : begin
             fib(2) : return 1
         fib(4) : fib(2) returned 1
         fib(4) == fib(3) + fib(2) == 2
         fib(4) : return 2
     fib(6) : fib(4) returned 2
     fib(6) == fib(5) + fib(4) == 5
     fib(6) : return 5
main: fib(6) returned 5

http://coliru.stacked-crooked.com/a/c83b4fe86ed8df04

[mynicks]

thanks