dslreports logo
site
 
    All Forums Hot Topics Gallery
spc

spacer




how-to block ads


Search Topic:
uniqs
7
share rss forum feed


stray

join:2000-01-16
Warren, NJ
reply to cplusnoob

Re: Please help me understand this function

Can't for the life of me figure out why this works - missing closing parenthesis, "}", empty includes, and no main().

Perhaps you could post the entire program??
--
V-Rtifacts - When Virtual Reality Was More Than Virtual



cplusnoob

@rr.com

Well that's odd. I did post the whole thing and I previewed and it all worked fined. I guess maybe it was trimmed when it got posted?

I'll take a look at your link Rob, I am reading a book now and so far it has been great but it doesn't explain how it works for some reason, just the output. Everything else up to this point has been explained very well.

cdru, I understand the purpose of the function, I just don't understand how it actually works to achieve the result. It's calling itself over and over with one less number each time until the number is 2. How are those answers being returned as the correct answer if the only way to break the cycle is by having the variable be 2?

I'll do some more research I guess. I have caught on really quick to everything up to this point and I just want to make sure I understand what the code is doing and not just copy / paste it.

Thanks again for the input.



cdru
Go Colts
Premium,MVM
join:2003-05-14
Fort Wayne, IN
kudos:7

said by cplusnoob :

cdru, I understand the purpose of the function, I just don't understand how it actually works to achieve the result. It's calling itself over and over with one less number each time until the number is 2. How are those answers being returned as the correct answer if the only way to break the cycle is by having the variable be 2?

It's calling the function recursively.

For values of 0 and 1, it sounds like you understand. If 2 is initially passed in, before it can return the value it calls the same function with n-1 (2-1 = 1) and n-2 (2-2=0). Those two calls return 1 and 0 respectively. It adds those up and returns the sum, 1.

For a more complicated example, pass in 6. That would make recursive calls to n=5 and n=4. Then 4, 3; 3, 2. Then 3, 2; 2, 1; 2, 1; 1, 0. Then 2, 1; 1, 0; 1, 0. Then 1, 0. Each call adding up the returned value then finally returning the final value to display.


cdru
Go Colts
Premium,MVM
join:2003-05-14
Fort Wayne, IN
kudos:7
reply to cplusnoob

said by cplusnoob :

I'll do some more research I guess. I have caught on really quick to everything up to this point and I just want to make sure I understand what the code is doing and not just copy / paste it.

There's 3 common ways (maybe more) that actually solve the calculation. Each one has their advantages and disadvantages.

The simplest/quickest algorithm to implement is the recursive algorithm that you're working with now. It's also the least efficient. The same function is called multiple times with the same value, and the extensive pushing and popping to the call stack kills the performance.

An improved algorithm instead of recursively starting at n and working there way down to 1. Instead it performs a definite loop from 1 to n, adding as it goes. It's still has to iterate over all n levels, but saves considerably due to the stack not growing very rapidly.
static int fib(int n)
{
    int u = 0;
    int v = 1;
    int i, t;
 
    for (i = 2; i <= n; i++)
    {
        t = u + v;
        u = v;
        v = t;
    }
 
    return v;
}
 

The fastest performance is just O(1), and reduces the computation to a single line of code.
static int fib(int n)
{
    return (int)((1 / Math.Sqrt(5)) * (Math.Pow(((1 + Math.Sqrt(5)) / 2), n) - Math.Pow(((1 - Math.Sqrt(5)) / 2), n)));
}
 

Calling the function recursively, for n = 1 to 50, run time was 946708 milliseconds. (over 15 minutes). Running for the same sample size, the other two functions did not even register 1 ms. I had to up the sample size to 1 to 10000 where looping was 274 ms and the single line function was 53 ms.

dave
Premium,MVM
join:2000-05-04
not in ohio
kudos:8

I would assume the whole point of the OP's code is that it's an exercise in understanding recursive activation, since (as you say) it's not a sensible approach to use otherwise.



cdru
Go Colts
Premium,MVM
join:2003-05-14
Fort Wayne, IN
kudos:7

said by dave:

I would assume the whole point of the OP's code is that it's an exercise in understanding recursive activation, since (as you say) it's not a sensible approach to use otherwise.

I would presume that too. But its one of the classic problems that are tackled multiple different ways showing that there's more then one method to tackle a problem, and that there are advantages and disadvantages for each method.