再帰的アルゴリズムの例_PHP チュートリアル

1.例 (C++ から記述):

行番号 プログラム

1 1 {if（w>o）

2 2 { コート<

3 3 p(w-1);

4 p(w-1);

5 }

6 }

終了

ステートメント p(4) を実行した後の出力結果: 4 3 2 1 1 2 1 1 3 2 1 1 2 1 1

2つ。説明:

1.再帰呼び出しの原理は、毎回呼び出される関数がそれ自体であることを除いて、通常の呼び出しと同じです。

2.スタック（ユーザースタック）を自分でプログラムして「再帰呼び出し」と同じ機能を実現することができます。

3. 3. 「再帰呼び出し」中、システムはスタック (システム スタック) を自動的にセットアップおよび管理します。

私たちの介入は必要ありませんが、これにより「再帰呼び出し」の謎が増大します。より良い方向へ

「再帰呼び出し」を完全に理解するために、システム スタックが表で表されるようになりました。

4. 「スタック」形式に関する注意事項

スタックの形式は次のとおりです:

正方形

スクエアb

スクエアc

関数呼び出し後に返される行番号
関数という名前
W
の値

関数が呼び出されるたびに、関数はスタックに「プッシュ」され、関数の実行後に 1 回「ポップ」されます

3．プログラム説明:

1. p(4) の呼び出しを開始します。この時点で実行されるステートメントは 1、2、3 です

終了

P(4)

4


p(4) のステートメント 2 を実行します: cout

ただし、ステートメント 3 のため、p(3) は実行中に呼び出す必要があります。p(3) が実行された場合にのみ、p(4) を実行し続けることができます。

2. P(3) の呼び出しを開始します。この時点で実行されるステートメントは 1、2、3 です

4

P(3)

3

終了
P(4)
4


p(3) が実行されると、p(4) のステートメント 4 が実行されます（四角 a に「4」を記入します）。

p(3) のステートメント 2 を実行します: cout<

上記の状況と同様に、ステートメント 3 が実行されると、p(2) が呼び出されなければなりません。p(2) が実行される場合にのみ、p(3) が実行され続けます。

3. P(2) の呼び出しを開始します。この時点で実行されるステートメントは 1、2、3 です

4

P(2)

2

4
P(3)
3

終了
P(4)
4


p(2) のステートメント 2 を実行します: cout

上記の状況と同様に、ステートメント 3 が実行されると、p(1) が呼び出されなければなりません。p(1) が実行された場合にのみ、p(2) が実行され続けます。

4. P(1) の呼び出しを開始します。この時点で実行されるステートメントは 1、2、3 です

4

P(1)

1

4
P(2)
2

4
P(3)
3

終了
P(4)
4


p(2) のステートメント 2 を実行します: cout

上記の状況と同様に、ステートメント 3 が実行されると、p(0) が呼び出されなければなりません。p(0) が実行される場合にのみ、p(1) が実行され続けます。

5． P(0) の呼び出しを開始します。この時点で実行されるステートメントは次のとおりです: 1

4

P(0)

0

4
P(1)
1

4
P(2)
2

4
P(3)
3

終了
P(4)
4


w=0 はステートメント 1 を満たさないため、ステートメント 5 と 6 に直接ジャンプします。そのため、p(0) が完了し、p(0) を「ポップ」する必要があります。

6．この時点で実行されるステートメントは次のとおりです: 4

4

P(1)

1

4
P(2)
2

4
P(3)
3

終了
P(4)
4

p(0) の実行が完了し、p(0) の二乗 a が 4 であるため、p(1) のステートメント 4 が引き続き実行されます。 p(1) は w の値が 1 であるため、p(0) が呼び出されます。

7. p(0) の呼び出しを開始します

5
P(0)
0

4
P(1)
1

4
P(2)
2

4
P(3)
3

終了
P(4)
4

p(0)の実行が終了すると、p(1)のステートメント5が実行されます(四角aに「5」を記入します)。

w=0 はステートメント 1 を満たさないため、ステートメント 5 と 6 に直接ジャンプします。そのため、p(0) が完了し、p(0) を「ポップ」する必要があります。

8．現時点で実行されるステートメントは次のとおりです: 5

4
P(1)
1

4
P(2)
2

4
P(3)
3

終了
P(4)
4

p(0) の実行が完了し、p(0) の二乗 a が 5 なので、p(1) のステートメント 5 (最後の文) が引き続き実行されるため、p(1) の実行は完了し、p(1) は「ポップ」操作を実行する必要があります。

9．

4
P(2)
2

4
P(3)
3

終了
P(4)
4

p(1) の実行が完了し、p(1) の平方 a が 4 であるため、p(2) のステートメント 4 が引き続き実行されます。 p(2) は w の値が 2 であるため、p(1) が呼び出されます。

10． P(1) の呼び出しを開始します。この時点で実行されるステートメントは 1、2、3 です

5
P(1)
1

4
P(2)
2

4
P(3)
3

終了
P(4)
4

p(1) が実行されると、p(2) のステートメント 5 が実行されます (四角 a に「5」を記入します)。

p(1) のステートメント 2 を実行します: cout

ステートメント 3 が実行されると、p(0) が呼び出されなければなりません。p(0) が実行される場合にのみ、p(1) が実行され続けることができます。

11． P(0) の呼び出しを開始すると、この時点で実行されるステートメントは次のとおりです: 1

4
P(0)
0

5
P(1)
1

4
P(2)
2

4
P(3)
3

終了
P(4)
4

w=0 はステートメント 1 を満たさないため、ステートメント 5 と 6 に直接ジャンプします。そのため、p(0) が完了し、p(0) を「ポップ」する必要があります。

12．この時点で実行されるステートメントは次のとおりです: 4

5
P(1)
1

4
P(2)
2

4
P(3)
3

終了
P(4)
4

p(0) の実行が完了し、p(0) の二乗 a が 4 であるため、p(1) のステートメント 4 が引き続き実行されます。 p(1) は w の値が 1 であるため、p(0) が呼び出されます。

13. p(0) の呼び出しを開始します

5
P(0)
0

5
P(1)
1

4
P(2)
2

4
P(3)
3

終了
P(4)
4

p(0)の実行が終了すると、p(1)のステートメント5が実行されます(四角aに「5」を記入します)。

w=0 はステートメント 1 を満たさないため、ステートメント 5 と 6 に直接ジャンプします。そのため、p(0) が完了し、p(0) を「ポップ」する必要があります。

14.現時点で実行されるステートメントは次のとおりです: 5

5
P(1)
1

4
P(2)
2

4
P(3)
3

終了
P(4)
4

p(0) の実行が完了し、p(0) の二乗 a が 5 なので、p(1) のステートメント 5 (最後の文) が引き続き実行されるため、p(1) の実行は完了し、p(1) は「ポップ」操作を実行する必要があります。

15.

4
P(2)
2

4
P(3)
3

終了
P(4)
4

p(1) の実行が完了し、p(1) の二乗 a が 5 であるため、p(2) のステートメント 5 (最後の文) が引き続き実行されるため、p(2) の実行は完了し、p(2) は「ポップ」操作を実行する必要があります。

注: 実際、ステップ 10 から 15 はすべて P(1) を呼び出すため、ステップ 4 から 9 を繰り返します

16.

4
P(3)
3

終了
P(4)
4

p(2) の実行が完了し、p(2) の二乗 a が 4 であるため、p(3) のステートメント 4 が引き続き実行されます。 p(3) は w の値が 3 であるため、p(2) が呼び出されます。

17. P(2) の呼び出しを開始します。この時点で実行されるステートメントは 1、2、3 です

5
P(2)
2

4
P(3)
3

終了
P(4)
4

p(2)の実行が終了すると、p(3)のステートメント5が実行されます(四角aに「5」を記入します)。

p(2) のステートメント 2 を実行します: cout

上記の状況と同様に、ステートメント 3 が実行されると、p(1) が呼び出される必要があります。p(1) が実行された場合にのみ、p(2) は実行を継続できます。

18. p(1) の呼び出しを開始します

省略…

注: 実際、ステップ 17 から 29 はすべて P(2) を呼び出すため、3 から 15 まで繰り返されます

このステップでは、 2 1 1 が再度出力されます (ステップ 3、4、10 を参照)

4つ。結論と分析:

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

結果
4
3
2
1
1
2
1
1
3
2
1
1
2
1
1

5 番目の結果は 4 番目の結果と重複しています。これは、両方とも p(1) を呼び出したためです

6 番目、7 番目、および 8 番目の結果は、3 番目、4 番目、および 5 番目の結果を繰り返します。これは、それらがすべて p(2) を呼び出したためです。

9 番目から 15 番目の結果は 2 番目から 8 番目の結果を繰り返しています。これは、それらがすべて p(3) を呼び出しているためです。

http://www.bkjia.com/PHPjc/477490.html

www.bkjia.comtru​​ehttp://www.bkjia.com/PHPjc/477490.html技術記事 1つ。例 (C++ から説明): 行番号プログラム 0 p (int w) 1 {if (wo) 2 { coutw; 3 p(w-1); 4 p(w-1); p(4) 後の出力結果: 4 3 2 1 1 2 1...