回答編集履歴
4
コード修正
test
CHANGED
|
@@ -10,7 +10,7 @@
|
|
|
10
10
|
|
|
11
11
|
~~「再帰」から「ループ」へと実装方式の切り替えにおける、~~
|
|
12
12
|
|
|
13
|
-
再帰呼び出しでの「スタックの役割」を果たします。
|
|
13
|
+
~~再帰~~ 関数呼び出しでの「スタックの役割」を果たします。
|
|
14
14
|
|
|
15
15
|
|
|
16
16
|
|
|
@@ -148,7 +148,7 @@
|
|
|
148
148
|
|
|
149
149
|
top = Node(1, Node(2, Node(3, None)))
|
|
150
150
|
|
|
151
|
-
print(search(top, 2))
|
|
151
|
+
print(search_recursive(top, 2))
|
|
152
152
|
|
|
153
153
|
print(search_loop(top, 2))
|
|
154
154
|
|
3
勘違いがあった点を修正
test
CHANGED
|
@@ -8,7 +8,7 @@
|
|
|
8
8
|
|
|
9
9
|
|
|
10
10
|
|
|
11
|
-
|
|
11
|
+
~~「再帰」から「ループ」へと実装方式の切り替えにおける、~~
|
|
12
12
|
|
|
13
13
|
再帰呼び出しでの「スタックの役割」を果たします。
|
|
14
14
|
|
|
@@ -60,4 +60,96 @@
|
|
|
60
60
|
|
|
61
61
|
再帰呼び出しの時に処理系内部で行われてるような「スタック操作」を、
|
|
62
62
|
|
|
63
|
-
独自にリストとループ処理で行う事で、再帰呼び出しを模倣しています。
|
|
63
|
+
独自にリストとループ処理で行う事で、再帰呼び出しを模倣 ~~しています。~~ 出来るようになります。
|
|
64
|
+
|
|
65
|
+
|
|
66
|
+
|
|
67
|
+
追記1:
|
|
68
|
+
|
|
69
|
+
- 現状のコードでは、スタックは直ぐに消化されているので、
|
|
70
|
+
|
|
71
|
+
再帰呼び出しを模倣しているわけではありません。
|
|
72
|
+
|
|
73
|
+
- 関数内での関数呼び出しを実装する時にスタックが必要になります。
|
|
74
|
+
|
|
75
|
+
|
|
76
|
+
|
|
77
|
+
追記2: 「再帰」から「ループ」へと実装方式の切り替えに関して
|
|
78
|
+
|
|
79
|
+
|
|
80
|
+
|
|
81
|
+
「連結リスト」のデータ構造の理解が学習のヒントです。
|
|
82
|
+
|
|
83
|
+
|
|
84
|
+
|
|
85
|
+
- 再帰では、引数を変えて同じ関数を実行します。
|
|
86
|
+
|
|
87
|
+
- ループで、引数を変えて同じ処理を実行に書き換え可能。
|
|
88
|
+
|
|
89
|
+
|
|
90
|
+
|
|
91
|
+
|
|
92
|
+
|
|
93
|
+
```python
|
|
94
|
+
|
|
95
|
+
class Node:
|
|
96
|
+
|
|
97
|
+
"""
|
|
98
|
+
|
|
99
|
+
Sample data:
|
|
100
|
+
|
|
101
|
+
+---------+--------+ +---------+--------+ +---------+------------+
|
|
102
|
+
|
|
103
|
+
| data: 1 | next: --> | data: 2 | next: --> | data: 3 | next: None |
|
|
104
|
+
|
|
105
|
+
+---------+--------+ +---------+--------+ +---------+------------+
|
|
106
|
+
|
|
107
|
+
"""
|
|
108
|
+
|
|
109
|
+
def __init__(self, data, next_node=None):
|
|
110
|
+
|
|
111
|
+
self.data = data
|
|
112
|
+
|
|
113
|
+
self.next = next_node
|
|
114
|
+
|
|
115
|
+
|
|
116
|
+
|
|
117
|
+
def __repr__(self):
|
|
118
|
+
|
|
119
|
+
return f"<Node data={self.data}>"
|
|
120
|
+
|
|
121
|
+
|
|
122
|
+
|
|
123
|
+
def search_recursive(node, value):
|
|
124
|
+
|
|
125
|
+
if node.data == value:
|
|
126
|
+
|
|
127
|
+
return node
|
|
128
|
+
|
|
129
|
+
else:
|
|
130
|
+
|
|
131
|
+
return search_recursive(node.next, value)
|
|
132
|
+
|
|
133
|
+
|
|
134
|
+
|
|
135
|
+
def search_loop(node, value):
|
|
136
|
+
|
|
137
|
+
while node:
|
|
138
|
+
|
|
139
|
+
if node.data == value:
|
|
140
|
+
|
|
141
|
+
return node
|
|
142
|
+
|
|
143
|
+
node = node.next
|
|
144
|
+
|
|
145
|
+
|
|
146
|
+
|
|
147
|
+
if __name__ == '__main__':
|
|
148
|
+
|
|
149
|
+
top = Node(1, Node(2, Node(3, None)))
|
|
150
|
+
|
|
151
|
+
print(search(top, 2))
|
|
152
|
+
|
|
153
|
+
print(search_loop(top, 2))
|
|
154
|
+
|
|
155
|
+
```
|
2
微修正
test
CHANGED
|
@@ -18,9 +18,7 @@
|
|
|
18
18
|
|
|
19
19
|
FILO (first-in-last-out) の PUSH と POP が list の append, pop
|
|
20
20
|
|
|
21
|
-
- 「関数」呼び出し時のコールスタック
|
|
21
|
+
- 「関数」呼び出し時のコールスタック, スタックフレーム
|
|
22
|
-
|
|
23
|
-
Python では Frame オブジェクト
|
|
24
22
|
|
|
25
23
|
- 「再帰」呼び出し時のスタック操作を、リストとループ処理で模倣する。
|
|
26
24
|
|
1
微修正
test
CHANGED
|
@@ -46,7 +46,7 @@
|
|
|
46
46
|
|
|
47
47
|
関数の戻り先の情報を積み上げていきます。(append)
|
|
48
48
|
|
|
49
|
-
- 関数が終わった時(return もしくは終端に到達)に
|
|
49
|
+
- 関数の実行が終わった時(return/raise もしくは終端に到達)に
|
|
50
50
|
|
|
51
51
|
スタックの一番上を取り除きます (pop)
|
|
52
52
|
|