C++ Recursion

[HyperSecret]

If you follow the link below it is the assignment I have to do.

http://staffwww.fullcoll.edu/sedwards/CS133/Announce/Announce.html#HW02_Rabbits

Rabbit (n) = (1 if n is 1 or 2) OR [Rabbit(n-1) + Rabbit(n-2); if n > 2]


The book gives this for an example code:



int rabbit(int n) {
if (n <= 2)
return 1;
else
return rabbit(n-1) + rabbit(n-2);
}


If you read the assignment you will see that I need to track when each 'n' enters and leaves the stack and what values are returned when they leave the stack.

I can't get the numbers 3+ to show 'Leaving Rabbit: n = 3 value = 2' etc...

I also can't figure out how to indent appropriately for the output...i know "\t" to tab but I don't know how to write something to figure out when and how many times...

my code:



int rabbit(int n) {
cout << "Enter Rabbit: n = " << n << endl;
if (n <= 2) {
cout << "Leave Rabbit: n = << n << " value = 1" << endl;
return 1;
} else {
return rabbit(n-1) + rabbit(n-2);
}
}


any help will be appreciated.

[nielsie95]

It will only output the "leaving string" if (n <= 2), so what's the problem?

Here's the flow of the program:

program Rabbit;

function rabbit(n, Counter: Integer): Integer;
var
s: string;
begin
s := StringOfChar(' ', Counter * 2);
WriteLn(s+'Enter Rabbit: '+IntToStr(n));
if (n <= 2) then
begin
WriteLn(s+'n <= 2');
Result := 1;
end
else
begin
WriteLn(s+'Passing though: '+IntToStr(n));
Result := rabbit(n-1, Counter + 1) + rabbit(n-2, Counter + 1);
WriteLn(s+'Result after passing: '+IntToStr(n));
end;
WriteLn(s+'Leaving Rabbit: '+IntToStr(n));
end;

begin
rabbit(5, 0);
end.



Enter Rabbit: 5
Passing though: 5
Enter Rabbit: 4
Passing though: 4
Enter Rabbit: 3
Passing though: 3
Enter Rabbit: 2
n <= 2
Leaving Rabbit: 2
Enter Rabbit: 1
n <= 2
Leaving Rabbit: 1
Result after passing: 3
Leaving Rabbit: 3
Enter Rabbit: 2
n <= 2
Leaving Rabbit: 2
Result after passing: 4
Leaving Rabbit: 4
Enter Rabbit: 3
Passing though: 3
Enter Rabbit: 2
n <= 2
Leaving Rabbit: 2
Enter Rabbit: 1
n <= 2
Leaving Rabbit: 1
Result after passing: 3
Leaving Rabbit: 3
Result after passing: 5
Leaving Rabbit: 5

[HyperSecret]

In C++ though it always exits the function on a return statement. Which means that it won't ever reach either of the last 2 Writeln's which is where my problem is =p

[HyperSecret]

Enter Rabbit: n = 4
Enter Rabbit: n = 3
Enter Rabbit: n = 2
Leave rabbit: n = 2 value = 1
Enter Rabbit: n = 1
Leave rabbit: n = 1 value = 1
Enter Rabbit: n = 2
Leave rabbit: n = 2 value = 1



This is my output right now with this code:



#include <iostream>
using namespace std;

int rabbit(int, int);

int main() {
int a = rabbit(4,0);
return 0;
}

int rabbit(int n, int indent) {
char p[] = "";
memset(p, ' ', indent * 3);
cout << p << "Enter Rabbit: n = " << n << endl;
if (n <= 2) {
cout << p << "Leave rabbit: n = " << n << " value = 1" << endl;
return 1;
} else {
return rabbit(n - 1, ++indent) + rabbit(n - 2, indent++);
}
}



I am missing the spots where it states that it is 'Leaving Rabbit: n =3,4 value = 2,3' respectively...

I don't know if there is a way to read the stack or something that I should be doing or what

[nielsie95]

That's because it also leaves in the else statement. You can just use a temporary variable to store rabbit(n - 1) + rabbit(n - 2) and then write+return it.

[HyperSecret]

That's because it also leaves in the else statement. You can just use a temporary variable to store rabbit(n - 1) + rabbit(n - 2) and then write+return it.

Yea, Method opened my eyes to that. I didn't realize you could assign a recursion statement to a variable and it still work properly. Every example in class and every example in the book has the recursive statement as:

return RecFunc();

Not one example showing or stateing that you can make a variable assignment with it. I should have realized this way sooner, I was just not thinking.

I sometimes get confused and don't think clearly when programming in languages I'm not fluent in. I worry more about how I am suppose to implement it and make it work in that language rather than thinking of what I CAN do.