Recursion

[vlad61]

hey guys! I am trying to tackle recursion - my teacher gave me a example problem showing the Fibonacci sequence done recursively and i was wondering if someone could please explain it step by step to me:

int fibanocci(int terms)
{

    if(terms == 1)
    {
        return 1;
    }

    else if (terms==2)
    {
        return 2;
    }


    else
    {
        return fibanocci(terms-1)+fibanocci(terms-2);
    }
}

the function takes in the term of the sequence you want to print out and finds what it equals to. we count the terms by: 1,2,3,5 = 1,2,3,4 just in case that's necessary information

[toexii]

Your function is actually wrong, have a quick look at the actual Fibonacci sequence and you'll notice:
http://en.wikipedia.org/wiki/Fibonacci_number

The sequence is: 0, 1, 1, 2, 3, 5, 8 etc...

But since the topic is recursion and not necessarily this particular sequence I'll use your function, you should just know that it's incorrect.

The first part should be obvious:

    if(terms == 1)
    {
        return 1;
    }

    else if (terms==2)
    {
        return 2;
    }

If the argument is 1, return the first term, in your case 1.
if the argument is 2, return the second term which in your case is 2.

The last part is the interesting part, the actual recursion:

 else
    {
        return fibanocci(terms-1)+fibanocci(terms-2);
    }

Here you start calculating the term that was originally given as an argument to the function. This term is made out of its previous two terms, thus you call the function that calculates a specific term(i.d. your function) with argument that are one term before the original, and two terms before the original. What actually happens is it calls fibonacci(terms-1), this gets an argument that is one lower than the original(at first call). It will then try to calculate that term, exactly the same way you are calculating the original term. It keeps repeating this process untill it has reached either term==1 or term==2, so it return either 1 or 2. Then it has an actual value to work with and it can calculate fibonacci(term-1) + fibonacci(term-2) and return that value, filling up the entire chain.

I hope this makes some sense, I am by no means a teacher, just trying to explain my thought process.

What may help you understand this, is by taking a term, say 5, and just write out everything that happens in your function.

[nand]

Hello,

I followed a tutorial on binary trees that contained recursion. It can be found at: http://cslibrary.stanford.edu/ .
Most notably, was problem 18 of the linked lists problem (RecursiveReverse()). I actually spent a few days and nights understanding it and it all became clear when I drew the pointers on paper for every "layer of recursion".

I always get confused by complicated explanations. I always think how a search program would function (say, total commander's search for a file):
- search in the first directory on a drive ( if the file is found, return; else reccur )
- search in the first subdirectory of that directory ( if the file is found, return; else reccur )
- search in the first subdirectory of that subdirectory of that directory ( if the file is found, return; else reccur )
- search in the first subdirectory of that subdirectory of that subdirectory of that directory ( if the file is found, return; else reccur )
and so on.

start from these two sentences:
1. Any recursive function is one that calls itself.
2. Any recursive function needs a "base case" so it can stop.

It also helped me to have this wallpaper at that time: http://www.zulkey.com/derivatives-thumb-315x400.jpg

[vlad61]

hello - i do try following what happens if i put a 5 into it and i cant seem to get an 8 out.

so-

fib(5)

becomes fib(4) + fib(3)

fib(4)

becomes fib(3) + fib(2)

fib(3)

becomes fib(2) + fib(1)

and then the other fib 3 from the beginning becomes also

fib(2) + fib(1) Ohhh....

So then i think in the end it equals to 2+1+2=5, and 2+1=3 and so together that makes 8..i think is that how it goes?

[Watachiaieto]

int fibanocci(int terms)
{

    if(terms == 0)
    {
        return 0;
    }

    else if (terms==1)
    {
        return 1;
    }


    else
    {
        return fibanocci(terms-1)+fibanocci(terms-2);
    }
}

there is the true fibanocci code (simply make it return 0 instead of 1 and 1 instead of 2)

[vlad61]

lol..it hardly matters how you start it thats not the point of this thread anyway. I know it starts with 011235

[shacktar]

So then i think in the end it equals to 2+1+2=5, and 2+1=3 and so together that makes 8..i think is that how it goes?

You got it.

Just to note, these:

if(terms == 1)
{
     return 1;
}

else if (terms==2)
{
     return 2;
}

are called the base cases which essentially tell the recursion when to stop. This is when the answer can be figured out directly. If there were no base cases, recursive function calls would result in an infinite loop.

Here is how you can view the call to fib(5):

fib(5) = { fib(4) + fib(3) }
       = { [ fib(3) + fib(2) ] + [ fib(2) + fib(1) ] }
       = { [ ( fib(2) + fib(1) ) + fib(2) ] + [ fib(2) + fib(1) ] }
       = { [ ( 2 + 1 ) + 2 ] + [ 2 + 1 ] }
       = { [ 3 + 2 ] + 3 }
       = { 5 + 3 }
       = 8

You can see that the base cases remove the need to expand fib(x) thus the final answer can be found without any more expansions.

[vlad61]

Hey thank you Shacktar - Im definitively starting to understand it but i also see that i need more practice on these its a bit different from things im used to