Recursive Algorithm Example_PHP Tutorial

1. Example (described from C++):

Line number Program

0 0 p (int w)

1 1 {if（ w>o）

2 2 { cout<

3 3 p(w-1);

4 p(w-1);

5 }

6 }

End

The print result after executing statement p(4): 4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

2. Description:

1． The principle of recursive calling is the same as that of ordinary calling, except that the function called each time is itself.

2． We can program the stack (user stack) ourselves to achieve the same function as "recursive call".

3． 3. During a "recursive call", the system will automatically set up and manage the stack (system stack), and

No need for our intervention, but this also increases the mystery of "recursive call". For the better

To understand "recursive call" clearly, the system stack is now represented in a table.

4． Some notes on the "stack" format

The format of the stack is:

square a
Square b
Square c

Line number returned after function call
Function called
The value of W

Every time a function is called, it is "pushed" onto the stack; after the function is executed, it is "popped" once

3. Program explanation:

1． Start calling p(4). The statements executed at this time are: 1, 2, 3

End
P(4)
4

Execute statement 2 of p(4): cout<

But because of statement 3, p(3) must be called during execution. Only when p(3) is executed, can p(4) continue to be executed.

2． Start calling P(3). The statements executed at this time are: 1, 2, 3

4
P(3)
3

End
P(4)
4

When p(3) is executed, statement 4 in p(4) will be executed (so fill in "4" in square a).

Execute statement 2 of p(3): cout<

Same as the above situation, when statement 3 is executed, p(2) must be called. Only when p(2) is executed, p(3) can continue to be executed.

3． Start calling P(2). The statements executed at this time are: 1, 2, 3

4
P(2)
2

4
P(3)
3

End
P(4)
4

Execute statement 2 of p(2): cout<

Same as the above situation, when statement 3 is executed, p(1) must be called. Only when p(1) is executed, can p(2) continue to be executed.

4． Start calling P(1). The statements executed at this time are: 1, 2, 3

4
P(1)
1

4
P(2)
2

4
P(3)
3

End
P(4)
4

Execute statement 2 of p(2): cout<

Same as the above situation, when statement 3 is executed, p(0) must be called. Only when p(0) is executed, can p(1) continue to be executed.

5． Start calling P(0), and the statements executed at this time are: 1

4
P(0)
0

4
P(1)
1

4
P(2)
2

4
P(3)
3

End
P(4)
4

Because w=0 does not satisfy statement 1, it jumps directly to statements 5 and 6, so that p(0) is completed and p(0) needs to be "popped".

6． The statements executed at this time are: 4

4
P(1)
1

4
P(2)
2

4
P(3)
3

End
P(4)
4

Since the execution of p(0) is completed, and the square a of p(0) is 4, so statement 4 of p(1) continues to be executed: p(w-1); and because the square p(1) The value of w in c is 1, so p(0) is called.

7． Start calling p(0)

5
P(0)
0

4
P(1)
1

4
P(2)
2

4
P(3)
3

End
P(4)
4

When p(0) is finished executing, statement 5 in p(1) will be executed (so fill in "5" in square a).

Because w=0 does not satisfy statement 1, it jumps directly to statements 5 and 6, so that p(0) is completed and p(0) needs to be "popped".

8. The statements executed at this time are: 5

4
P(1)
1

4
P(2)
2

4
P(3)
3

End
P(4)
4

Since the execution of p(0) is completed, and the square a of p(0) is 5, statement 5 (the last sentence) of p(1) continues to be executed, so the execution of p(1) is completed, p(1 ) to perform a "pop" operation.

9.

4
P(2)
2

4
P(3)
3

End
P(4)
4

Since the execution of p(1) is completed, and the square a of p(1) is 4, so statement 4 of p(2) continues to be executed: p(w-1); and because the square p(2) The value of w in c is 2, so p(1) is called.

10． Start calling P(1). The statements executed at this time are: 1, 2, 3

5
P(1)
1

4
P(2)
2

4
P(3)
3

End
P(4)
4

When p(1) is executed, statement 5 in p(2) will be executed (so fill in "5" in square a).

Execute statement 2 of p(1): cout<

When statement 3 is executed, p(0) must be called. Only when p(0) is executed, can p(1) continue to be executed.

11． Start calling P(0), and the statements executed at this time are: 1

4
P(0)
0

5
P(1)
1

4
P(2)
2

4
P(3)
3

End
P(4)
4

Because w=0 does not satisfy statement 1, it jumps directly to statements 5 and 6, so that p(0) is completed and p(0) needs to be "popped".

12． The statements executed at this time are: 4

5
P(1)
1

4
P(2)
2

4
P(3)
3

End
P(4)
4

Since the execution of p(0) is completed, and the square a of p(0) is 4, so statement 4 of p(1) continues to be executed: p(w-1); and since the square p(1) The value of w in c is 1, so p(0) is called.

13. Start calling p(0)

5
P(0)
0

5
P(1)
1

4
P(2)
2

4
P(3)
3

End
P(4)
4

When p(0) is finished executing, statement 5 in p(1) will be executed (so fill in "5" in square a).

Because w=0 does not satisfy statement 1, it jumps directly to statements 5 and 6, so that p(0) is completed and p(0) needs to be "popped".

14． The statements executed at this time are: 5

5
P(1)
1

4
P(2)
2

4
P(3)
3

End
P(4)
4

Since the execution of p(0) is completed, and the square a of p(0) is 5, statement 5 (the last sentence) of p(1) continues to be executed, so the execution of p(1) is completed, p(1 ) to perform a "pop" operation.

15.

4
P(2)
2

4
P(3)
3

End
P(4)
4

Since the execution of p(1) is completed, and the square a of p(1) is 5, statement 5 (the last sentence) of p(2) continues to be executed, so the execution of p(2) is completed, p(2 ) to perform a "pop" operation.

Note: In fact, steps 10 to 15 repeat steps 4 to 9, because they all call P(1)

16.

4
P(3)
3

End
P(4)
4

Since the execution of p(2) is completed, and the square a of p(2) is 4, so statement 4 of p(3) continues to be executed: p(w-1); and since the square p(3) The value of w in c is 3, so p(2) is called.

17. Start calling P(2). The statements executed at this time are: 1, 2, 3

5
P(2)
2

4
P(3)
3

End
P(4)
4

When p(2) is executed, statement 5 in p(3) will be executed (so fill in "5" in square a).

Execute statement 2 of p(2): cout<

Same as the above situation, when statement 3 is executed, p(1) must be called. Only when p(1) is executed, can p(2) continue to be executed.

18. Start calling p(1)

Omit...

Note: In fact, steps 17 to 29 are repeated from 3 to 15, because they all call P(2)

In this step, 2 1 1 is printed (see steps 3, 4, 10)

4. Conclusion and analysis:

Steps
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Result
4
3
2
1
1
2
1
1
3
2
1
1
2
1
1

The 5th result duplicates the 4th result, this is because they both called p(1)

The 6th, 7th, and 8th results repeat the 3rd, 4th, and 5th results. This is because they all called p(2)

The 9th to 15th results repeat the 2nd to 8th results because they all called p(3)