Introduction to PHP recursive algorithms and applications

Introduction to PHP recursive algorithms and applications_PHP tutorial

WBOY

Release： 2016-07-15 13:28:20

Original

908 people have browsed it

PHP is the preferred technology for developing dynamic page WEB. We must keep its basic knowledge in mind so that it can help with programming. Let’s take a look at what’s going on with the PHP recursive algorithm.

1. The meaning of calling subroutine:

When the main program executes the statement of calling subroutine A, the system saves some necessary on-site data, and then executes something like The GOTO statement in BASIC language jumps to subroutine A (to make it simpler, I ignore the parameter passing process here). When subprogram A reaches the statement calling subprogram B, the system will jump to subprogram B as above. After subprogram B finishes executing all the statements, it jumps back to subprogram A and calls the next statement of subprogram B (I have ignored the return value processing again). After subprogram A finishes executing, it jumps back to the main program and calls subprogram A. The next statement of the statement, the main program is executed to the end. Let’s make a comparison: when I was eating (executing the main program), someone called me (executing the subroutine A) while I was eating. Halfway through, the phone rang again (executing the subroutine B). I just had to answer it first. After finishing the phone call, finishing talking to someone, and finally finishing the meal (I am quite tired from eating this meal).

2. Understand recursive functions

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

Find n! We can put n! This definition means that 3 is required! , we must first find 2! , request 2! , you must first find 1! , request 1! , you must first find 0! , and 0!=1, so 1!=0!*1=1, and then find 2!, 3!. Represented by functions respectively, we can observe that except calculating 0! Except for subprograms, other subprograms are basically similar. We can design such a subprogram:

<ol class="dp-xml">
<li class="alt"><span><span>int factorial(int i){  </span></span></li>
<li class=""><span>int res;  </span></li>
<li class="alt">
<span></span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">factorial</font></span><span>(I-1)*i;  </span>
</li>
<li class=""><span>return res;  </span></li>
<li class="alt"><span>} </span></li>
</ol>

Copy after login

Then when the main program statement s=factorial( 3), factorial(3) will be executed, but when 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, But its data area in memory is two copies! When factorial(2) is executed, factorial(1) will be called, and factorial(1) will be called factorial(0). Each time the factorial function is called, it will add a new data area in the memory, so these copies You can understand multiple functions as multiple functions with different names; but there is a problem with our function. When factorial(0) is executed, it will call factorial(-1). . . Causes an infinite loop, that is to say, in the factorial function, we must ensure that the function is no longer called at the appropriate time, that is, the call statement res=factorial(I-1)*i; is not executed. So the function needs to be changed to:

<ol class="dp-xml">
<li class="alt"><span><span>int factorial(int i){  </span></span></li>
<li class=""><span>int res;  </span></li>
<li class="alt">
<span>if (I</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>0) </span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">factorial</font></span><span>(I-1)*i; else </span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">1</font></span><span>;  </span>
</li>
<li class=""><span>return res;  </span></li>
<li class="alt"><span>} </span></li>
</ol>

Copy after login

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 loop accumulation method for this problem. If you want to use the recursive method here, you must consider two points:
1) whether the problem can be transformed into a recursive description;
2) whether there are boundary conditions for the end of the recursion.

Obviously both conditions for recursion are present:

<ol class="dp-xml">
<li class="alt"><span><span>1） s(n) =s(n-1)+n  </span></span></li>
<li class=""><span>2） s(1)=1 </span></li>
</ol>

Copy after login

So the source program is:

<ol class="dp-xml">
<li class="alt"><span><span>int progression(int n){  </span></span></li>
<li class=""><span>int res;  </span></li>
<li class="alt">
<span>if (</span><span class="attribute"><font color="#ff0000">n</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">1</font></span><span> )</span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">1</font></span><span> else </span><span class="attribute"><font color="#ff0000">res</font></span><span>=</span><span class="attribute-value"><font color="#0000ff">progression</font></span><span>(n-1)+n;  </span>
</li>
<li class=""><span>return res;  </span></li>
<li class="alt"><span>} </span></li>
</ol>

Copy after login

4. Application of recursion

In-order traversal of a binary tree

<ol class="dp-xml">
<li class="alt"><span><span>void inorder (BinTree T){  </span></span></li>
<li class=""><span>if (T){  </span></li>
<li class="alt">
<span>inorder(T-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>lchild);  </span>
</li>
<li class="">
<span>printf(“%c”,T-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>data);  </span>
</li>
<li class="alt">
<span>inorder(T-</span><span class="tag"><strong><font color="#006699">></font></strong></span><span>rchild);  </span>
</li>
<li class=""><span>}  </span></li>
<li class="alt"><span>} </span></li>
</ol>

Copy after login