反復解を再帰的解に変換する一般的な式はありますか？

Question

私は繰り返しソリューションを再帰的なものに変えなければならないラボに苦労しています。

私は再帰に本当に苦労しています。私はそれを考えていますが、試行錯誤よりも良い方法がなければならないと感じています。

私は超進歩したプログラマーではないので、私はあまり良くありませんが、ほとんどの時間に合う金型があれば好奇心が強いです。

フィードバックが高く評価されました。私はJavaのベストを知っているので、Javaの面であれば、本当に助けになるでしょう！

Answer 1

一般的に反復ソリューションは、フォーマットに減少させることができます。

function recursive(information): 
    if(condition) then 
     modify information 
     recursive(information) 
    else 
     return some value 
    end if 
end function 

が、これは覚えておいてください：フォーマットがあるので

function iterative(information): 
    while (condition) do 
     modify information 
    end while 
    return some value 
end function 

これは、コードを再配置することにより、再帰関数に変更することができます非常に一般的な公式であり、あなたはまだ（ほとんどの）いくつかの問題について多くの作業を行う必要があります。

最終的な注：繰り返しソリューションは、しばしば最適な方法です。再帰の使用はメモリ上で悪化し、一般にパフォーマンスが悪化します。ほとんどの場合、読んだり、理解したり、実装したりすることがより簡単になるように使用されています（デプス・ファースト・サーチはこれの良い例です。繰り返しアルゴリズムと再帰アルゴリズムを調べてください）。あなたが1つのことを教えられているからといって、それが最善の方法であるという意味ではなく、追加の研究をして、あなた自身のためにテストすることを確かめているからです。

Answer 2

私は反復解を再帰的解に変換するラボの考え方を嫌います。反復的な解決策がある場合は、通常はそれを使用する方がよいでしょう。

しかし、反復解が反復の間にたくさんの状態を保存していれば - 多くの状態 - それはおそらく再帰でうまくいくでしょう。

これを行うための「一般的な式」はありません。より小さな同一の問題に分けることができる問題に直面したときの再帰の可能性について考える。

ハードドライブ上のすべてのファイルに対して何かを行うことを検討してください。これを繰り返し行うことはできますが、保存しなければならないすべての状態を描くのは難しいですし、それぞれのフォルダに何かしたい場合は扱いにくくなる可能性があります。再帰的解は "z：各ファイルについて、各フォルダーのx、yとz（またはzとy）を実行する" "です。

階乗とは対照的に、反復で階乗を行うことはできますが、反復解は簡単なので、例として使用することさえ気にしません。しかし、私は、概念的には、より小さな同一の問題で構成されている問題の別のケースであると考えています。

これは助けになるかどうかわかりませんが、それは私の考え方です。

Answer 3

私の意見では、問題を機能的に同じだが小さいものにする一連の操作を適用できる問題がある場合は、再帰のみを使用してください。

ハードドライブ上のファイルを数えれば、それを繰り返し実行できますが、かなり面倒です。しかし、問題を機能的に同じだが小さいものにする一連の操作を適用することは問題です。カレントディレクトリのみのファイルを数え、サブディレクトリの数を追加することができます。だから、一般的には

、あなたはこのような観点からあなたの問題を記述することができる場合：

function fixTheProblem(thingToFix) { 
    if (problemCanBeFixedDirectly) // IE no more subdirectories 
     return calculateProblemResult(); // IE Count files in current directory 
    else { 
     var result = calculateSmallSubProblem(); // IE count files in current 
     var smallerButSimilarProblems = breakupProblem(); // IE take subdirecties 
     foreach (var smallerProblem in smallerButSimilarProblems) { 
      var intermediateResult = fixTheProblem(smallerProblem); 
      result += intermediateResult; 
     } 
     return result; 
    } 
}