Introduction to PHP recursive algorithm and application methods

PHP is the preferred technology for developing WEB for dynamic pages, and we need to keep the basics in mind to make it easier to program. Let's take a look at the PHP recursive algorithm.

1. Meaning of calling subroutine:

When the main program executes to the calling subroutine A statement, the system saves some necessary live data, and then executes the GOTO statement similar to BASIC, jumping to the subroutine A (for simplicity's sake, I'm ignoring parameter passing here). When the subroutine A executes to the calling subroutine B statement, the system does the same, jumping to the subroutine B. After the subroutine B executes all the statements, it jumps back to the subroutine A calls the next statement of the subroutine B statement (I have ignored the return value processing). After the subroutine A executes, it jumps back to the next statement of the subroutine A statement, and the main program executes to the end. Compare this: when I'm halfway through a meal (executing the main program), someone calls me (executing the subroutine A), and halfway through the conversation, the phone rings again (executing the subroutine B). All I have to do is answer the phone first, finish the conversation with someone, and finally finish the meal (I've had enough of J).

2. Understand recursive functions

We all learned mathematical induction in high school, PHP recursion for example:

Beg n! We can put n! So if you define it this way, you're asking for 3 factorial. We have to solve for 2 factorial. 2 factorial. I have to do 1 factorial first. So 1 factorial I have to get 0 factorial. , and 0! Is equal to 1, so 1 factorial = 0. Times 1 is 1, and then we have 2 factorial. , 3! . Let's write it as a function, and we can observe that we divide by 0! Subroutine, other subroutine is basically similar, we can design such a subroutine:

int factorial(int i){
int res;
res=factorial(I-1)*i;
return res;
}
When the main program statement s=factorial(3) is executed, factorial(3) is executed, but factorial(2) is called when factorial(3) is executed. At this point, please note that factorial(3) and factorial(2) are the same code segment, but they have two data areas in memory! When factorial(2) is executed, factorial (1) is called, factorial (0) is called, factorial (1) is called, factorial function is called once, it will add a data area in memory, so these multiple copies of the function, you can think of it as a number of different names of functions to understand; But we have a problem with this function. When factorial (0) is executed, it calls factorial (-1)... In other words, in the factorial function, we need to make sure that we don't call the function again at the appropriate time, that is, we don't execute res=factorial(I-1)*i; This call statement. So the function is going to be:

int factorial(int i){
int res;
if (I > 0) res=factorial(I-1)*i; else res=1;
return res;
}
3. How to use the PHP recursive algorithm to solve the problem

Example: please s = 1 + 2 + 3 + 4 + 5 + 6 +... We used to use the method of cyclic accumulation for this problem. Here, if you want to use a recursive method, you must consider two things:
1) can convert the problem into a recursive description;
2) whether there is a boundary condition for the end of recursion.

Obviously we have two conditions for recursion:

(1) s n) = s (n - 1) + n
2) s (1) = 1
Therefore, the source program is:

int progression(int n){
int res;
if (n=1 )res=1 else res=progression(n-1)+n;
return res;
}
4. Application of recursion

The middle order traverses the two-fork tree

void inorder (BinTree T){
if (T){
inorder(T- > lchild);
c printf (" % ", T - > data);
inorder(T- > rchild);
}
}