問題描述
是否可以僅使用 for 循環來實現包含 for 循環的遞歸函數,該循環包含對上述函數的調用? (Can a recursive function containing a for loop that contains a call of the mentioned function be implemented using only for loops?)
已經提出了類似的問題,並且普遍的共識是任何東西都可以從遞歸轉換為 for 循環,反之亦然。但是,我找不到將以下偽代碼類型的函數轉換為 for 循環的方法:
def recursive(n):
if n == 0:
return
for i in range(some_number):
do_sth...
recursive(n‑1)
在這種情況下,有 n 個嵌套循環,n 根據給定的參數而變化。當僅使用 for 循環時,嵌套循環的數量似乎總是在代碼中預先確定,它不會因“輸入”而異。有沒有辦法只使用 for 循環來製作這樣的東西?
參考解法
方法 1:
Is there a way to make something like this using only for loops?
Well, if you admit a while loop as a case of a pseudocode for loop, at least your example can be made:
def nonrecursive(n):
a = []
z = 0
while n:
while n:
i = z
if i == some_number: break
print((n, i))
a += [[n, i]]
n ‑= 1
z = 0
if not a: break
n, i = a.pop()
i += 1
z = i
方法 2:
We need to be careful here.
The general true statement is that loops can replace recursion and vice versa. This can be shown lots of ways; see the structured programming theorem for ideas.
Whether for loops can replace recursion depends upon your definitions. Can your for loops run forever, or for an indefinite amount of time not known in advance? If so, they are functionally equivalent to while loops, and they can replace recursion. If your for loops cannot be made to run forever or for an unknown (initially) number of iterations, recursion cannot always be replaced.
Really, it's while loops (plus a stack data structure) that can replace recursion without much trouble.
(by corchizzo、Armali、Patrick87)