Day 5 recursive
Today we learn to recurrent this common proposition. From this proposition, we learn such a special data structure: tree. This concept is attracted when learning mathematics, indicating a function that can be represented by ourselves. A relatively popular definition is: call itself.
One of the most common examples is to step:
1 n = 0;
F (n) =
F (n-1) n> = 1;
If calculated directly, you can use a loop: for (n = 1, s = 1; n <= n; n ) s * = N; this is also calculated according to mathematical definition, but puts these two expressions together It also requires a human thinking integration process. The following uses the recursive method can be more intuitive representation:
INT FAC (INT N)
{
IF (n == 0) Return 0;
Return N * FAC (N-1);
}
We have done a lot in high school and universities, and we need to find F (n) = q (n) * f (n-1) such a problem solved (Q (n) is relatively better calculation). The use of recursive can use the more concurrent code expressing programmer in the computer, and good recursive efficiency is not bad (its function call the underlying mechanism is implemented using the lower stack). It can be seen that recursive can always find an equivalent non-creation algorithm. And most of the FOR cycles can be converted into a recursive.
Use recursive needs to be aware of its recursive depth. This can lead to our recursive unable to complete.
Let's take a look at the basic structure of recursive:
1. It needs to solve a basic situation: such as the top 0! = 1
2, each recursion requires approaching the basic situation: N! = (N-1)! * n;
The correctness of this recursive we can use the inductive method to prove that the direct use of the step by the step is not need to prove it.
There is a hyperpinrate called cow problem:
If a small cow, from the fourth year of birth, a small cow every year, and how many cows are in the nine
This problem can express the way of thinking about people using recursive methods. We need to find a mathematical equation representing the number of cows when resolving this issue.
In the past 3 years, there is no new calf to become a mother. So 3 years later, there is constant calf to become a mother. Let's write this expression: N years, the number of cattle is = N-3 Number of bulls N-1 Number of cattle.
Number of N-3 ago is really a number of cattle moms in N-1.
And when there is n = 1, the number of cattle is count. Such analysis, it can be used to solve the problem with the formula above.
CPP recursive implementation:
// this function is write by zhouhuahai (Prairie) in 9cbs
INT getnumber (int years) {if (Years <4 && years> = 0) Return 1; Else Return GetNumber (YEARS-1) GetNumber (Years-3);
There is also a non-recurrent algorithm, you can compare.
// this function Write by Pomelowu (Warrior) in 9cbs
INT getBaby (int N) {int sum = 0;
IF (n> = 4) {for (int i = 1; i <= n - 4 1; i ) {SUM ; SUM = Getbaby (i); // Although not recursive here but also call I still have recursive ingredients}} Return Sum;
The above two programs come from the two friends of 9CBS. This problem discussed for a long time on the Chinaunix sector. Interested friends can take it. Address: http://www.chinaunix.net/jh/23/130156.html
Leave an exercise for everyone: Fibonacci number: 1, 1, 2, 3, 5, 8, 13 ... Please give the Nth recursive algorithm for this number. Do not write the answer, go to Google on your own Search, too much.
