Fibonacci Rabbits that don't die

Question

A pair of newly born rabbits (one male, one female) is put in a field. Rabbits are able to mate at the age of one month so that at the end of the second month each pair produces two new pairs of rabbits and then dies.

Note: In month 0, there are 0 pairs of rabbits. In month 1, there is 1 pair of rabbits.

1. Write a program – using a while loop – that takes the number of months from the user and prints the number of pairs of rabbits at the end of that month.

2. In the same cpp file, write a recursive function rabbits() that takes the number of months as input and returns the number of pairs of rabbits at the end of that month.

3. In the main program, call the function rabbits() with the number that the user entered. Output both calculations (i.e. the one you obtained with the loop and the one that the recursive function returns) and see if they are equal.

---

The description is fairly self explanatory. I already have the main program down (regular Fibonacci function), but I can't figure out how to implement the rabbits dying after reproducing. I already know that every other month, the number of rabbits doubles, but I don't know how to implement it. Thanks in advance.

#include <iostream>
using namespace std;

int rabbits (int);

int main ()
{
int x, month, result, counter = 0, rab_now, rab_lastmonth = 1, rab_twomonthsago = 0;

cout << "Please enter the month \n\n";
cin >> month;
cout << "\n";

result = rabbits (month);

while (counter <= month - 1)
{
      rab_now = rab_lastmonth + rab_twomonthsago;

      x = rab_lastmonth;
      rab_lastmonth = rab_now;
      rab_twomonthsago = x;

      counter++;
}

cout << "At the end of month " << month << ", there will be " << rab_lastmonth << "      
pairs of rabbits" << endl;

system("PAUSE");
return 0;
}

int rabbits (int month)

{
if (month == 0)
{
    return 0;
}
else if (month == 1)
{
    return 1;
}
else
{
    return (rabbits (month + 1) + rabbits (month - 2));
}
}

Answer 1

Your function is almost correct, there’s just one trivial mistake – probably a typo:

return (rabbits (month + 1) + rabbits (month - 2));

– you want the rabbits from the previous month, not the next month. Change the + to a -:

return (rabbits (month - 1) + rabbits (month - 2));

And there ya go.

Incidentally, try calling that function with a larger month number – such as 20 or 30. Do you notice anything regarding the performance? Especially compared to the iterative implementation? Can you think of a way to implement the recursive function more efficiently (brain teaser: this isn’t trivial unless you already know how to approach this).