Recursion

[NoUserNameHere]

How would I trace the steps for the function's output?

int f(int n)
{
	if (n==0)
		return 1;
	else if(n==1)
		return 2;
	else
		return 2* f(n-2) + f(n-1);
}

Would it be something like:
(Let's say n=6)

step 1) 2 * f(6-2) + f(6-1)
2) 2 * f(4-2) + f(5-1)
3) 2 * f(2-1) + f(4-1)
4) 2 * f(1-1) + f(3-1)
Then stop after step 4 since it reached the base case and then return it from step 4 to 1?

[Taywin]

If you want a step number, you need to pass the number to the function as well unless you have a global variable (which should not be there).

To display what you are at, you could simply print out what you are trying to do before you return the value. And the step display won't be exactly what you wrote down... So just try it to see what it display. You need to play around with it. :)

[NoUserNameHere]

Not sure if I worded my first post properly, but what I want to do is be able to figure out the output on paper as practice for an exam.

[pseudorandom21]

hehe the Visual Studio debugger was made for this sort of thing also, link to youtube video is in my signature if you can stand my horrible voice I show you how to start using it.

[Taywin]

Not sure if I worded my first post properly, but what I want to do is be able to figure out the output on paper as practice for an exam.

Well, how about insert a print out in each line inside the function, and then run it? If you want to see each step, just add a new line to each print out. This is a very simple and primitive way of debugging and is still being used (no IDE required). Don't forget to add curly bracket if there are two or more lines of code inside if-else statement...

int f(int n) {
  // cout or print out the value of n
  if (n==0)
    // cout or print out that it hit the base case n==0
    return 1;
  else if(n==1)
    // cout or print out that it hit the base case n==1
    return 2;
  else
    // cout or print out that the whole call below but not really call the function
    // something like "2*f("+(n-2)+") + f("+n-1+")" ???
    return 2* f(n-2) + f(n-1);
}