Fibonacci rabbits that don't die

Question

A pair of newborn rabbits (one man, one woman) is placed in the field. Rabbits can mate at the age of one month, so at the end of the second month each pair creates 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.

• Write a program - using a while loop - which takes several months from the user and prints the number of pairs of rabbits at the end of this month.

• In the same cpp file, write the recursive function rabbits (), which takes the number of months as input and returns the number of rabbit pairs at the end of this month.

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

---

The description is pretty clear. I already have the main program down (regular Fibonacci function), but I can’t figure out how to implement rabbits dying after playing. I already know that every two months the number of rabbits doubles, but I do not 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 is only one trivial error - perhaps a typo:

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

- You want rabbits compared to the previous month, and not next month. Change + to a - :

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

And here you go.

By the way, try calling this function with a large month number - for example, 20 or 30. Have you noticed anything regarding performance? Especially compared to iterative implementation? Can you come up with a way to more effectively implement a recursive function (brain teaser: this is not trivial if you don’t already know how to approach this).