Recursive method of C++ basic algorithm thought

Recursion is a very common algorithm, which is widely used in mathematical calculation. The recursion method is suitable for the situation where there is obvious rule of formula.

The basic idea of recursion
Recursive method is a kind of rational thinking on behalf of the moss, according to the existing data and relationships, and gradually to get results. The execution process of recursive method is as follows:

(1) solve the intermediate results according to the known results and relations.

(2) determine whether the requirements are met, if not, continue to solve the intermediate results according to the known results and relationships. If the requirement is met, a correct answer is found.

Recursion requires the user to know the logical relationship between the answer and the question. In many mathematical problems, there is a clear formula to follow, so it can be realized by recursion.

Examples of recursion
The Fibonacci sequence in mathematics is a classic example of using recursion.

In the abacus, written in the 13th century by the Italian mathematician Fibonacci, the typical birth problem of a rabbit is described as follows:

If a pair of one-month-old rabbits can have a pair of bunnies every month after that, and a pair of newborn rabbits can have a pair of bunnies after two months. That is, they are born in January and start having babies in March. So assuming no rabbit deaths in one year, how many pairs of rabbits are there after one year?

1. Recursive algorithm
Let's analyze the litter problem of rabbits. So let's look at the log of rabbits month by month.

Month 1:1 pair of rabbits;

Month 2:1 pair of rabbits;

Month 3:2 pairs of rabbits;

Month 4:3 pairs of rabbits;

Month 5:5 pairs of rabbits;

Month 6:8 pairs of rabbits;

...........................

And you can see from the top, from month three, the total log of rabbits in each month is equal to the sum of rabbits in the previous two months. The corresponding calculation formula is as follows:

The total number of rabbits in the NTH month Fn=Fn-1+Fn-2.

Here, the number of rabbits in the first month F1 is equal to 1, and the number of rabbits in the second month F2 is equal to 1.

You can solve it using a recursive formula. For the convenience of general type, we can write an algorithm to calculate the Fibonacci number series problem. According to this consideration, we can write the corresponding algorithm to solve the rabbit birthing problem. The sample code is as follows:

 
int Fibonacci(n)
{
 int t1,t2;
 if(n>0)
 {
  if(n==1||n==2)
  {
   return 1;
  }
  else
  {
   t1=Fibonacci(n-1);
   t2=Fibonacci(n-2);
   return t1+t2;
  } 
 }
 else
 {
  return 0;
 }
}

Recursive algorithm to solve the rabbit litter problem
With the rabbit litter problem algorithm, we can solve any such problem. Here is the complete code for solving the rabbit litter problem:

#include<iostream>
using namespace std;
 
int Fibonacci(int n)
{
 int t1,t2;
 if(n>0)
 {
  if(n==1||n==2)
  {
   return 1;
  }
  else
  {
   t1=Fibonacci(n-1);   //Recursive call gets F of n minus 1.
   t2=Fibonacci(n-2);   //Recursive call gets F of n minus 2.
   return t1+t2;
  } 
 }
 else
 {
  return 0;
 }
}
int main()
{
 int n,num;
 cout<<" Recursive method to solve the litter problem of rabbits: "<<endl;
 cout<<" Please enter time: "<<endl;
 cin>>n;
 num=Fibonacci(n);
 cout<<" after "<<n<<" Months later, "<<endl;
 cout<<" The number of rabbits is: "<<num<<" right "<<endl;
 return 0; 
}

Execute the program, the user enters 12, and the following results are obtained:

< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201310/201310140844395.jpg ">