アルゴリズム:5ステップで再帰を解消します
52761 ワード
背景
再帰は解析問題に有利であるが,再帰に基づく実現効率は高くなく,関数スタックサイズの制限により再帰の階層にも制限がある.本稿では、分析フェーズで再帰的な考え方を採用し、実装フェーズで非再帰的なアルゴリズムを採用することができるように、再帰的な除去の一般的な手順を示します.
関数の呼び出しプロセス
関数の呼び出しはスタックに基づいており、呼び出すたびに次の操作が行われます.呼び出し開始時:戻りアドレスとローカル変数がスタックに格納されます. 呼び出し終了時:スタックを出て、スタックに入ったときの戻りアドレスに戻ります.
スタックに割り当てられたスタックを使用して再帰を除去する
再帰バージョン
コード#コード#
非再帰バージョン
コード#コード#
消去プロセス
ステップ1:再帰バージョンのコードアドレスを識別するの最初の代表:元のメソッド呼び出し. 逆数の最初の代表:元のメソッド呼び出しが終了しました. の2番目の代表:メソッド呼び出しエントリ. の最後から2番目の代表:メソッド呼び出し出口. 再帰バージョンの各再帰呼び出しは、コードアドレスを定義する.
再帰的にn回呼び出された場合、コードアドレスは:n+4である.
ステップ2:スタックフレームの定義
スタックフレームはコード実行のコンテキストを表し、再帰バージョンのコードボディで使用されるローカル値タイプ変数をスタックフレームのメンバー変数として定義します.なぜ参照タイプは私が言わなくてもいいのか、また戻りアドレスメンバー変数を定義する必要があります.
ステップ3:whileループ
whileループの前にstack、currentReturnValue、currentAddressを宣言します.
ステップ4:switch文.
ステップ5:caseコードボディを塗りつぶします.
再帰バージョンのコードを次のように変換します.関数呼び出し使用:stack.push(new StackFrame{...}); およびcurrentAddress=2. で参照するローカル変数は、例えば、n、stackとなる.Peek().n . return文は、currentReturnValue=1になります.およびcurrentAddress=4; . 逆数の最初のcaseコード体は、return currentReturnValueである.
最終的な効果は上記の例です.
ハノータ練習
二叉木遍歴練習
この練習は私が以前採用した方法で見て、思想は上とよく似ています.
コメント
企業の応用をするには、このような再帰を解消するアルゴリズムは使えないはずだが、勉強が終わってから再帰に対する理解も明らかになった.
再帰は解析問題に有利であるが,再帰に基づく実現効率は高くなく,関数スタックサイズの制限により再帰の階層にも制限がある.本稿では、分析フェーズで再帰的な考え方を採用し、実装フェーズで非再帰的なアルゴリズムを採用することができるように、再帰的な除去の一般的な手順を示します.
関数の呼び出しプロセス
関数の呼び出しはスタックに基づいており、呼び出すたびに次の操作が行われます.
スタックに割り当てられたスタックを使用して再帰を除去する
再帰バージョン
コード#コード#
1 public static int Triangle(int n)
2 {
3 // ：2
4 if (n == 1)
5 {
6 // ：4
7 return n;
8 }
9
10 /*
11 * ：4 ：3
12 * / /
13 * / /
14 * / / */
15 return n + Triangle(n - 1);
16 }非再帰バージョン
コード#コード#
1 private class StackFrame
2 {
3 public int N;
4 public int ReturnAddress;
5 }
6
7 public static int Triangle2(int n)
8 {
9 var stack = new Stack<StackFrame>();
10 var currentReturnValue = 0;
11 var currentAddress = 1;
12
13 while (true)
14 {
15 switch (currentAddress)
16 {
17 case 1:
18 {
19 stack.Push(new StackFrame
20 {
21 N = n,
22 ReturnAddress = 5
23 });
24 currentAddress = 2;
25 }
26 break;
27 case 2:
28 {
29 var frame = stack.Peek();
30 if (frame.N == 1)
31 {
32 currentReturnValue = 1;
33 currentAddress = 4;
34 }
35 else
36 {
37 stack.Push(new StackFrame
38 {
39 N = frame.N - 1,
40 ReturnAddress = 3
41 });
42 currentAddress = 2;
43 }
44 }
45 break;
46 case 3:
47 {
48 var frame = stack.Peek();
49 currentReturnValue = frame.N + currentReturnValue;
50 currentAddress = 4;
51 }
52 break;
53 case 4:
54 {
55 currentAddress = stack.Pop().ReturnAddress;
56 }
57 break;
58 case 5:
59 {
60 return currentReturnValue;
61 }
62 }
63 }消去プロセス
ステップ1:再帰バージョンのコードアドレスを識別する
再帰的にn回呼び出された場合、コードアドレスは:n+4である.
1 public static int Triangle(int n)
2 {
3 // ：2
4 if (n == 1)
5 {
6 // ：4
7 return n;
8 }
9
10 /*
11 * ：4 ：3
12 * / /
13 * / /
14 * / / */
15 return n + Triangle(n - 1);
16 }ステップ2:スタックフレームの定義
スタックフレームはコード実行のコンテキストを表し、再帰バージョンのコードボディで使用されるローカル値タイプ変数をスタックフレームのメンバー変数として定義します.なぜ参照タイプは私が言わなくてもいいのか、また戻りアドレスメンバー変数を定義する必要があります.
1 private class StackFrame
2 {
3 public int N;
4 public int ReturnAddress;
5 }ステップ3:whileループ
whileループの前にstack、currentReturnValue、currentAddressを宣言します.
1 public static int Triangle2(int n)
2 {
3 var stack = new Stack<StackFrame>();
4 var currentReturnValue = 0;
5 var currentAddress = 1;
6
7 while (true)
8 {
9 }
10 }ステップ4:switch文.
1 public static int Triangle2(int n)
2 {
3 var stack = new Stack<StackFrame>();
4 var currentReturnValue = 0;
5 var currentAddress = 1;
6
7 while (true)
8 {
9 switch (currentAddress)
10 {
11 case 1:
12 {
13 }
14 break;
15 case 2:
16 {
17 }
18 break;
19 case 3:
20 {
21 }
22 break;
23 case 4:
24 {
25 }
26 break;
27 case 5:
28 {
29 }
30 }
31 }
32 }ステップ5:caseコードボディを塗りつぶします.
再帰バージョンのコードを次のように変換します.
最終的な効果は上記の例です.
ハノータ練習
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 namespace DataStuctureStudy.Recursives
8 {
9 class HanoiTest
10 {
11 public static void Hanoi(int n, string source, string middle, string target)
12 {
13 if (n == 1)
14 {
15 Console.WriteLine(String.Format("{0}->{1}", source, target));
16 }
17 else
18 {
19 Hanoi(n - 1, source, target, middle);
20 Console.WriteLine(String.Format("{0}->{1}", source, target));
21 Hanoi(n - 1, middle, source, target);
22 }
23 }
24
25 public static void Hanoi2(int n, string source, string middle, string target)
26 {
27 var stack = new Stack<StackFrame>();
28 var currentAddress = 1;
29
30 while (true)
31 {
32 switch (currentAddress)
33 {
34 case 1:
35 {
36 stack.Push(new StackFrame
37 {
38 N = n,
39 Source = source,
40 Middle = middle,
41 Target = target,
42 ReturnAddress = 5
43 });
44 currentAddress = 2;
45 }
46 break;
47 case 2:
48 {
49 var frame = stack.Peek();
50 if (frame.N == 1)
51 {
52 Console.WriteLine(String.Format("{0}->{1}", frame.Source, frame.Target));
53 currentAddress = 4;
54 }
55 else
56 {
57 stack.Push(new StackFrame
58 {
59 N = frame.N - 1,
60 Source = frame.Source,
61 Middle = frame.Target,
62 Target = frame.Middle,
63 ReturnAddress = 3
64 });
65 currentAddress = 2;
66 }
67 }
68 break;
69 case 3:
70 {
71 var frame = stack.Peek();
72 Console.WriteLine(String.Format("{0}->{1}", frame.Source, frame.Target));
73 stack.Push(new StackFrame
74 {
75 N = frame.N - 1,
76 Source = frame.Middle,
77 Middle = frame.Source,
78 Target = frame.Target,
79 ReturnAddress = 4
80 });
81 currentAddress = 2;
82 }
83 break;
84 case 4:
85 currentAddress = stack.Pop().ReturnAddress;
86 break;
87 case 5:
88 return;
89 }
90 }
91 }
92
93 private class StackFrame
94 {
95 public int N;
96 public string Source;
97 public string Middle;
98 public string Target;
99 public int ReturnAddress;
100 }
101 }
102 }二叉木遍歴練習
この練習は私が以前採用した方法で見て、思想は上とよく似ています.
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 namespace DataStuctureStudy.Recursives
8 {
9 class TreeTest
10 {
11 public static void Test()
12 {
13 RecursiveTraverse(Node.BuildTree());
14 StackTraverse(Node.BuildTree());
15 }
16
17 private class Node
18 {
19 public Node Left { get; set; }
20
21 public Node Right { get; set; }
22
23 public int Value { get; set; }
24
25 public static Node BuildTree()
26 {
27 return new Node
28 {
29 Value = 1,
30 Left = new Node
31 {
32 Value = 2,
33 Left = new Node
34 {
35 Value = 3
36 },
37 Right = new Node
38 {
39 Value = 4
40 }
41 },
42 Right = new Node
43 {
44 Value = 5,
45 Left = new Node
46 {
47 Value = 6
48 },
49 Right = new Node
50 {
51 Value = 7
52 }
53 }
54 };
55 }
56 }
57
58 private static void RecursiveTraverse(Node node)
59 {
60 if (node == null)
61 {
62 return;
63 }
64
65 RecursiveTraverse(node.Left);
66 Console.WriteLine(node.Value);
67 RecursiveTraverse(node.Right);
68 }
69
70 private enum CodeAddress
71 {
72 Start,
73 AfterFirstRecursiveCall,
74 AfterSecondRecursiveCall
75 }
76
77 private class StackFrame
78 {
79 public Node Node { get; set; }
80
81 public CodeAddress CodeAddress { get; set; }
82 }
83
84 private static void StackTraverse(Node node)
85 {
86 var stack = new Stack<StackFrame>();
87 stack.Push(new StackFrame
88 {
89 Node = node,
90 CodeAddress = CodeAddress.Start
91 });
92
93 while (stack.Count > 0)
94 {
95 var current = stack.Peek();
96
97 switch (current.CodeAddress)
98 {
99 case CodeAddress.Start:
100 if (current.Node == null)
101 {
102 stack.Pop();
103 }
104 else
105 {
106 current.CodeAddress = CodeAddress.AfterFirstRecursiveCall;
107 stack.Push(new StackFrame
108 {
109 Node = current.Node.Left,
110 CodeAddress = CodeAddress.Start
111 });
112 }
113 break;
114 case CodeAddress.AfterFirstRecursiveCall:
115 Console.WriteLine(current.Node.Value);
116
117 current.CodeAddress = CodeAddress.AfterSecondRecursiveCall;
118 stack.Push(new StackFrame
119 {
120 Node = current.Node.Right,
121 CodeAddress = CodeAddress.Start
122 });
123 break;
124 case CodeAddress.AfterSecondRecursiveCall:
125 stack.Pop();
126 break;
127 }
128 }
129 }
130 }
131 }コメント
企業の応用をするには、このような再帰を解消するアルゴリズムは使えないはずだが、勉強が終わってから再帰に対する理解も明らかになった.