再帰とは何ですか？どのように使用しますか？

再帰は楽しいプログラミングの概念ですが、学ぶのが少し難しい場合があります。再帰とは、単にそれ自体を繰り返すものを意味します。再帰の生意気な例を見たい場合は、Googleで再帰を検索してみてください。検索結果の提案が再帰的であるイースターエッグが見つかります。一方、再帰関数のコーディング方法を学びたい場合は、読み進めてください。

再帰関数とは何ですか？

再帰関数は、それ自体を呼び出す関数です。基本的に、関数を使用してループを作成します。ご想像のとおり、これらは書くのが難しい関数になる可能性があります。コードを永久に実行したくはありません。

ループと同様に、再帰関数は条件によって制御されます。条件が満たされると、関数はそれ自体の呼び出しを停止し、ループを停止します。これは、永久に実行せずに自分自身を呼び出す関数を作成する方法です。

再帰関数はループのように機能しますが、コンピューターによって実行される方法は異なります。したがって、一部のアルゴリズムはループ内でより効率的であり、他のアルゴリズムは再帰関数の恩恵を受けます。ただし、再帰関数の使用方法を検討する前に、再帰関数の記述方法を知っておく必要があります。

再帰関数の書き方

すべての再帰関数の基本構造は同じです。

FUNCTION name IF condition THEN RETURN result ELSE CALL FUNCTION name END FUNCTION

上記の例は擬似コードで書かれています。これは、任意の言語に適用できる関数の構造の概要を示しています。簡単にするために、この記事ではPythonに焦点を当てます。

再帰関数について最初に注意することは、条件が満たされると、関数が再帰を終了することです。つまり、再帰関数を作成するときに最初に決定したいのは、再帰をいつ停止するかです。

条件が満たされない場合、関数はそれ自体を呼び出します。したがって、次のループに情報を送信する場合は、関数の引数として送信する必要があります。これにより、再帰関数にさらに強力な機能を与えることができます。

関連：プログラミングの機能とは何ですか？

Pythonでの再帰関数の例

再帰が実際に動作しているのを見ると、再帰がどのように機能するかを理解するのがはるかに簡単になります。それを示すために、数値の階乗を返す再帰関数を書いてみましょう。

階乗は、数値とその前のすべての整数の積を返します。たとえば、5の階乗は5 x 4 x 3 x 2 x1または120です。

def factorialFunction(numberToMultiply): if numberToMultiply == 1 : return 1 else : return numberToMultiply * factorialFunction(numberToMultiply - 1) result = factorialFunction(3) print(result) //Outputs: 6

上記のプログラムでは、結果6が得られます。これは、数値3の階乗です。これは、最初は少し混乱する可能性があります。プログラムを段階的に実行すると役立ちます。

1. 関数が呼び出されると、numberToMultiplyは3になります。
2. 条件が満たされていないため、else条件に入ります。
3.  関数は3 *を返しますが、その後一時停止します。自分自身を呼び出して、返される残りの値を判別する必要があります。
4. 今回関数が呼び出されると、numberToMultiplyの値は2になります。
5. 条件が満たされていないため、else条件に入ります。
6. 関数は2 *を返しますが、その後一時停止します。自分自身を呼び出して、返される残りの値を判別する必要があります。
7. 関数が再度呼び出されます。今回は、numberToMultiplyの値は1になります。
8. 私たちのif条件が満たされています。関数は1を返します。
9. これで、ステップ6の関数は、ステップ3の関数に2 * 1を返すことができます。
10. ステップ3の関数は、3 * 2 * 1、つまり6を返すことができます。

再帰はトリッキーな概念です。ある関数を別の関数の上にスタックすることと考えると役立つ場合があります。1つの関数が最終的に解決されると、すべての関数が答えを得るまで、情報をスタックに送り返すことができます。

これは実際にはあなたのコンピュータがしていることとほとんど同じです。関数を呼び出すと、返されるまでメモリに保持されます。これは、再帰関数がループよりもはるかに多くのメモリを使用できることを意味します。

したがって、ループを再帰関数として記述するのは効率的ではないかもしれませんが、ループの構築を練習するための優れた方法です。ループを再帰関数としてコーディングして、同様の結果を得ることができるはずです。

ループを再帰関数に変換する方法の例

print("Enter an even number:") i = int(input()) while (i % 2) != 0 : print("That number is not even. Please enter a new number:") i = int(input())

このループは、次のように再帰的に記述することもできます。

def recursiveFunction(number) : if (number % 2) == 0 : return number else: print("That number is not even. Please enter a new number:") recursiveFunction(int(input())) print("Enter and even number:") i = recursiveFunction(int(input()))

最初のステップは、関数をいつ停止するかを決定することです。この場合、偶数を入力すると停止します。この例では、numberはユーザーの入力を追跡します。偶数を入力した場合は、その数値を返します。それ以外の場合は、引き続き新しい番号をお尋ねします。

ループを設定するために、関数を再度呼び出します。ただし、今回は、次の関数に渡す番号は、ユーザーが入力した新しい番号です。次の関数呼び出しは番号をチェックします。

これは本当に悪い機能です！はい、ループのように数が偶数かどうかをチェックしていますが、効率的ではありません。ユーザーが奇数を入力するたびに、関数はメモリに保持され、新しい関数が呼び出されます。これを十分な回数行うと、メモリが不足します。

関連：速く学ぶのに役立つ基本的なPythonの例

再帰関数の実際の例

上記の例は、再帰を使用しない場合の良い例です。では、再帰はどこで使用されますか？再帰を使用する場合の良い例は、二分木を検索することです。

データが二分木で構造化されている場合、データを検索するには多くのパスをたどる必要があります。ツリーの各ポイントで、右または左のどちらで検索を続行するかを決定する必要があります。訪問したツリーのどの部分を変数に保存することもできますが、再帰関数はその情報を自然に追跡できます。

上のツリーで6番目の数字を探していると想像してください。ツリーを左から右に検索する再帰関数を作成できます。アルゴリズムは次のようになります。

FUNCTION searchTree(branchToSearch) IF find 6 OR end of tree THEN RETURN result ELSE PROCESS branch CALL FUNCTION searchTree(left) CALL FUNCTION searchTree(right) END FUNCTION

この擬似コードの例では、アルゴリズムは最初にツリーの左側を検索します。新しい番号にアクセスするたびに、関数は一時停止され、メモリに保持されます。これにより、私たちがどこにいたかを追跡することができます。

アルゴリズムは常に最初に可能な限り左側を検索します。ツリーの終わりに達すると、searchTree（左）が完了し、右側をチェックします。両側がチェックされると、検索は1つのブランチをバックアップし、右側をチェックし続けます。

アルゴリズムがツリー全体を検索する場合、次の順序で検索します。

2、7、2、6、5、11、5、9、および4

上記の擬似コードを使用してフォローできるかどうかを確認してください。

再帰のレビュー

再帰は高度なトピックです。理解するには時間がかかり、コーディングが上手になるにはさらに時間がかかります。再帰関数を段階的に説明すると役立ちます。各関数呼び出しの表現を学習するときに、関数を実行するときに、インデックスカードや付箋を積み重ねると役立つ場合があります。

再帰関数を作成するときは、関数を終了する方法を決定することから始めます。次に、ループの設定方法を決定します。次の関数呼び出しに送信する必要のある情報と、返す必要のある情報を特定します。

再帰を学ぶための最良の方法は、それを実践し、あなたの過ちから学ぶことです。古いコードのいくつかを見て、ループを再帰関数として書き直すことに挑戦してください。コードの効率が上がることはないでしょうが、それは良い習慣です。