2つの再帰呼び出しを含む関数を中間関数に変換する

Question

2つの再帰呼び出しを持つ関数がありますが、これを反復関数に変換しようとしています。私はそれをどこで簡単に行うことができるのか分かりましたが、他の呼び出しを組み込む方法を理解することはできません。

機能：

def specialMultiplication(n): 
    if n < 2: 
     return 1 
    return n * specialMultiplication(n-1) * specialMultiplication(n-2) 

私はちょうどそれらのいずれかを持っていた場合、それは本当に簡単に次のようになります。

def specialMult(n, mult = 1): 
    while n > 1: 
     (n, mult) = (n-1, n * mult) # Or n-2 for the second one 
    return mult 

私はただの中で2番目の呼び出しを追加する方法を見つけ出すことはできません全体的に正しい答えを得る。ありがとう！

Answer 1

アルゴリズムの構造をもう少し変更しても構わない場合は、最小値から開始してボトムアップで値を計算できます。

def specialMultiplication(max_n): 
    a = b = 1 
    for n in range(1, max_n+1): 
     a, b = b, a*b*n 
    return b 

Answer 2

補助 "ToDoリスト" を使用して、反復関数に再帰を変換しますn >= 2場合

def specialMultiplication(n): 
    to_process = [] 
    result = 1 
    if n >= 2: 
     to_process.append(n) 
     while to_process: # while list is not empty 
      n = to_process.pop() 
      result *= n 
      if n >= 3: 
       to_process.append(n-1) 
       if n >= 4: 
        to_process.append(n-2) 
    return result 

1. がnしばらく
リストに追加し、
3. （to_process）作業リストを作成to_processは空ではなく、リストから項目をポップし、結果に掛ける
4. n-1 < 2の場合はpe rform「左」の操作を実行していない、
5. n-2 < 2場合（リストを仕事に追加されません）、「右」の操作

この方法は、消費するという利点を有している（リストを仕事に追加されません）少ないスタック。私は1から25の値の再帰的なバージョンに対して結果をチェックしていて、それらは等しい。

複雑さがO(2^n)なので、それはまだ遅いので、n=30（nが1増加すると時間が2倍になる）から実際に遅くなり始めていることに注意してください。 n=28は私のラップトップで12秒後に計算されます。

フラッドフィルアルゴリズムを実行するときにスタックオーバーフローの問題を修正するためにこのメソッドを使用しましたが、Fatal Python error: Cannot recover from stack overflow. During Flood Fillですが、Blcknghtの答えは、最初から計算する方法を再考するため、より適合しています。

Answer 3

OPの機能だけF0、F1、およびGのための異なる値で、フィボナッチルーカス関数と同じ再帰的構造を有する：

f(0) = f0 
f(1) = f1 
f(n) = g(f(n-2), f(n-1), n) 

これはrecurrence relationの一例です。ここでは、nステップでf（n）を計算する一般的な解の反復バージョンを示します。ボトムアップテール再帰に相当します。

def f(n): 
    if not isinstance(n, int): # Can be loosened a bit 
     raise TypeError('Input must be an int') # Can be more informative 
    if n < 0: 
     raise ValueError('Input must be non-negative') 
    if n == 0: 
     return f0 
    i, fi_1, fi = 1, f0, f1 # invariant: fi_1, fi = f(i-1), f(i) 
    while i < n: 
     i += 1 
     fi_1, fi = fi, g(fi_1, fi, n) # restore invariant for new i 
    return fi 

Blckknightの答えはあなたのアルゴリズムの実行時間が指数関数的である。この