プログラミングの経験がある人は、再帰関数をよく知っているはずです。再帰アルゴリズムは、ほとんどの問題に対して非常に効果的であり、注意すべき点がいくつかあります。再帰を使用する場合:
1) 再帰とは、関数自体の中で関数自体を呼び出すことです。
2) 再帰は効率が比較的低いため、時間制限がある場合には使用しないことをお勧めします。
3) 再帰プロセスには明確な終了条件、つまり再帰終了が必要です。
以下、再帰関数について詳しく説明していきます。
まず、例を通して再帰の簡単な使用法を見てみましょう。
m=int(input('数値を入力してください:'))deftest(x):x+=2ifx<100:test(x)else:print('最後の x は:',x)test(m)
出力は次のとおりです。
数値を入力してください: 20、最後の x は: 100
この例を分析してみましょう。まず、コードの最初の行で、m が test() メソッドに実際のパラメータとして渡され、x が追加されます。最初に 2 を実行し、次に A 判定を行って、x の値が 100 未満の場合は、この関数を再度呼び出します。呼び出し時に、x の現在の値が呼び出しに参加するための実際のパラメータとして使用されます。x> になると再帰が終了します。 =100を満たす。
以下の図を見てください。
つまり、条件を満たさない場合は最外層に戻り、この関数を呼び出します。
再帰アルゴリズムの古典的な問題について話すとき、フィボナッチ数列とハノイの塔は常に切り離すことができません。ここでは、再帰を使用してフィボナッチ数列を解く方法について説明します。
まず第一に、フィボナッチ数列の再帰公式は F(n)=F(n-1)+F(n-2) であり、F(1) と F(2) は 1 であることを知る必要があります。再帰を使用して、フィボナッチ数列内の項目の値を見つけることができます。
フィボナッチ数列の問題を解決するために使用できる方法はたくさんあります。
まず、一般的に使用される再帰的手法を使用して、この問題を解決します。
N=int(input(取得する項目数を入力:))deffibonacci(n):ifn<=2:#2以下の場合はnを1に設定 return1else:returnfibonacci(n-1) +fibonacci(n-2)print ('対応する値は',fibonacci(n))
出力は次のとおりです。
取得したいアイテムの数を入力してください: 4 は 3 に対応します
この再帰呼び出しメソッドでは、値 4 を入力すると、次の操作が再帰的に実行されます。
フィボナッチ(3)+フィボナッチ(2)=フィボナッチ(2)+フィボナッチ(1)+フィボナッチ(2)
すると、第 4 項の値は 1+1+1=3 であることがわかります。
実際、この問題を解決するには、時間の代わりに空間を使用することもできます。
コードは次のとおりです。
n=int(input(取得する項の数を入力:))fibonacci=[1,1]foriinrange(2,n):fibonacci.append(fibonacci[i-1]+fibonacci[i-2])print (' 対応する値は ',fibonacci[n-1])
出力は次のとおりです。
取得したいアイテムの数を入力してください: 4 は 3 に対応します
このようにして、最初にリストの最初の 2 つの項目の値を指定し、次に解決したい項目の数 n について、数式を通じて必要な項目をフィボナッチ数のリストに直接入力します。そして最後に、インデックス値に従って、対応する出力結果を直接見つけます。
再帰関数については以上です。多くの場合、再帰メソッドを使用すると、再帰終了と時間制限に特別な注意を払う必要があります。指定された時間を超えている場合は、問題を解決するために考え方を変える必要があります。上記の 2 番目の方法は、誰でも問題を解決するのに役立ちます。