As the preferred technology for developing dynamic page WEB, we must keep in mind its basic knowledge, which can help programming. Let's take a look at what the PHP recursive algorithm is.
1. The meaning of calling a subroutine:
When the main program executes to call subroutine A statement, the system saves some necessary field data, and then executes GOTO statements similar to BASIC language, jump to subroutine A (to be simpler, I ignore the process of parameter passing here). When subroutine A executes to call subroutine B statement, the system practices as above and jumps to subroutine B. After subroutine B has executed all statements, it jumps back to the next statement in the statement in the subroutine A called subroutine B (I have ignored the return value processing again). After subroutine A is executed, it jumps back to the next statement in the statement in the main program calling subroutine A, and the main program executes until the end. To make a comparison: When I was halfway through the meal (executing the main program), someone called me (executing the subroutine A), and when the words were halfway through, the phone rang again (executing the subroutine B). I just had to answer the phone first, then finish the conversation with someone, and finally finish the meal (I was tired enough to eat this meal).
2. Understand recursive functions
We all learned mathematical induction in high school, such as PHP recursive algorithm:
Please n! We can put n! This definition means 3! , we must first find 2! , Requires 2! , you must first ask for 1! , Require 1! , you must first ask for 0! , and 0!=1, so 1!=0!*1=1, and then find 2!, 3!. We can observe that we use functions to calculate 0 in addition to calculating! Except for subroutines, other subroutines are basically similar. We can design such a subroutine:
int factorial(int i){
int res;
res=factorial(I-1)*i;
return res;
}
Then when the main program statement s=factorial(3), factorial(3) will be executed, but when the factorial(3) is executed, factorial(2) will be called. At this time, everyone should note that although factorial(3) and factorial(2) are the same code segment, their data areas are two in memory! Factorial(2) will be called again, and factorial(0) will be called again. Every time factorial(1) will be called again, it will add a new data area to the memory. Then, these functions that have copied multiple copies can be understood as multiple functions with different names; but our function has some problems. When executing factorial(0), it will call again. . . Create a dead loop, that is, in factorial function, we must ensure that the function will not be called at appropriate times, that is, the call statement res=factorial(I-1)*i; will not be executed. So the function needs to be changed to:
int factorial(int i){
int res;
if (I>0) res=factorial(I-1)*i; else res=1;
return res;
}
3. How to consider using PHP recursive algorithm to solve the problem
Example: Find s=1+2+3+4+5+6+...+n Originally, we used to use the method of loop accumulation in this problem. If you want to use a recursive method, you must consider two points:
1) Can the problem be transformed into a recursive form of description;
2) Whether there is a boundary condition for recursive ending.
Obviously, there are two conditions for recursion:
1） s(n) =s(n-1)+n
2） s(1)=1
So the source program is:
int progression(int n){
int res;
if (n=1 )res=1 else res=progression(n-1)+n;
return res;
}
4. Recursive application
In-order traversal of binary trees
void inorder (BinTree T){
if (T){
inorder(T->lchild);
printf(“%c”,T->data);
inorder(T->rchild);
}
}