Help with recursion

[frogboy77]

I wrote this test code trying to work out a problem. The code gives the correct answer for the example (zero) but to understand the problem i need to understand what the code is doing on a sort of step by step basis. In other words how to do it with a pen and paper.
The answer is 3240 i just don't know why. Can anyone help?

#include <iostream>

using namespace std;

int fun(int n);
int a=50;
int b=2000;
int c=40;


int main()
{
    cout<<fun(0)<<endl;

    return 0;
}

int fun(int n)
{
    if(n>b) return n-c;
    if(n<=b) return fun(a+fun(a+fun(a+fun(a+n))));
}

[sergent]

Its just simple arithmetical operations. Use your common sense.

#include <iostream>

using namespace std;

int fun(int n);
int a=50;
int b=2000;
int c=40;


int main()
{
    cout<<fun(0)<<endl;

    return 0;
}

int fun(int n)
{
     cout << "N is " << n << "\n"; // Output what N is
    if(n>b) return n-c;
    if(n<=b) return fun(a+fun(a+fun(a+fun(a+n))));
}

This will output the N each time through your function, which may help you understand it.

[frogboy77]

Ok then using your "common sense" what is the answer if n=2000? Without the program.
"Simple" is relative. I also know how to write an output line.

[VernonDozier]

The first step is to get the non-varying "variables" out of there.

int fun(int n)
{
    if(n>2000) return n-40;
    if(n<=2000) return fun(50+fun(50+fun(50+fun(50+n))));
}

Second step is to simplify it by getting rid of the second if.

int fun(int n)
{
    if(n>2000)
    {
        return n-40;
    }
    return fun(50+fun(50+fun(50+fun(50+n))));
}

Third step is to realize that you picked N is 2000, which is the borderline case. You should also notice that when N is big, the return value will return something smaller than N and when N is small the function will return something bigger. Also notice that 40 and 50 are fairly close to each other, so your likely to get a value that's fairly close to 2000 at the end of it all. Looks like the whole thing can be simplified to a NON-recursive function. A few smart test cases (way bigger than 2000, way smaller than 2000, and "close to" 2000) should give you a pretty exact pattern. But that's cheating. Take pencil and paper, dust off the algebra cob-webs and solve the equation.

Pass it a small number like 500 and you'll always get the bottom case. You can never return till you get to the TOP case, which means you're ALWAYS going to return at least 1961.

[VernonDozier]

>> I also know how to write an output line.

The point is that that particular output line gives you the call stack and let's you see how it changes and how many times the function is called for different values, which shows the pattern.

[predator78]

1. fun(0) zero is passed in
2. that means n <= b would be true
3. if that is true then fun(50+fun(50+fun(50+fun(50+0))))
4. like math parethesis first? fun(50) can disregaurd add zero
5. that's once through keep going or let the comp do work :).

[frogboy77]

Thanks for the help (particularly Vernon, i think i should have made the variables const, and i wanted to play around with them so didn't want to retype all values into the function again so made them global). If anyone is interested here's the whole problem.
I know it can't be done by brute force but i wanted to get the idea behind the formula.