是否可以將如下所示的遞回函式轉換為完全迭代的函式？
def fact(n):
if n <= 1:
return
for i in range(n):
fact(n-1)
doSomethingFunc()
給定堆疊或佇列等額外空間似乎很容易，但我想知道我們是否可以在 O(1) 空間復雜度中做到這一點？
請注意，我們不能執行以下操作：
def fact(n):
for i in range (factorial(n)):
doSomethingFunc()
因為它需要非常量的記憶體來存盤factorial(n).
uj5u.com熱心網友回復：
嗯，一般來說沒有。我的意思是，遞回函式在堆疊中占用的空間不僅僅是這種編程風格的不便。它是計算所需的記憶體。
所以，當然，對于很多演算法來說，這個空間是不必要的，可以節省下來。例如，對于經典階乘
def fact(n):
if n<=1:
return 1
else:
return n*fact(n-1)
所有 n, n-1, n-2, ..., 1 引數的堆疊并不是真正必要的。所以，當然，你可以找到一個擺脫它的實作。但這就是優化（例如，在終端遞回的特定情況下。但我很確定您添加“doSomething”以明確您不想專注于該特定情況）。通常，您不能假設存在不需要所有這些值的演算法，遞回或迭代。否則，這就是說所有演算法都存在于 O(1) 空間復雜度版本中。
示例：正整數的基本表示
def baseRepr(num, base):
if num>=base:
s=baseRepr(num//base, base)
else:
s=''
return s chr(48 num
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/513170.html