再帰は興味深いプログラミングの概念ですが、習得するのは少し難しいです。再帰とは簡単に言えば、それ自体を繰り返すということです。再帰の生意気な例を見たければ、Googleで再帰を検索してみてください。検索結果が再帰を示唆するイースターエッグを見つけることができます。一方、再帰的な関数の書き方を学びたい人は、ぜひ読んでみてください。

再帰的関数は何ですか？

再帰的関数とは、自分自身を呼び出す関数のことです。実質的には、関数を使ったループを作ることになります。ご想像の通り、これらの関数は書くのが難しいです。コードが永遠に実行されることを望んでいない。

ループと同様に、再帰的な関数は条件によって制御されることになる。条件が満たされると、この関数は自分自身を呼び出すのを止め、ループを停止します。このように、自分自身を呼び出して、永遠に実行されない関数を作るのです。

再帰的関数はループと似たような働きをするが、コンピュータの実行方法は異なる。その結果、ループを使った方が効率的なアルゴリズムもあれば、再帰的な関数を使った方が有利なアルゴリズムもあります。しかし、再帰的関数の使い方を見る前に、再帰的関数の書き方を知っておく必要があります。

再帰的関数の書き方

すべての再帰的関数は、同じ基本構造を持っています。

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

上記の例は、疑似コードで書かれています。関数の構造を概説したもので、どの言語にも適用できる。簡単のために、この記事ではPythonに絞って説明します。

再帰的な関数について、まず注意しなければならないのは、関数が条件を満たしたときに再帰を抜けるということです。つまり、再帰的な関数を書くときは、まず再帰をいつ止めるかを決めることが重要です。

条件を満たさない場合、この関数は自分自身を呼び出します。したがって、次のループに情報を送る場合は、関数の引数として送らなければならない。これにより、再帰的関数の機能をより高めることができる。

関連：プログラミングにおける関数とは？

Pythonでの再帰的関数の例

再帰の仕組みを理解するには、実際に動いているところを見ると、より簡単に理解できます。それを実証するために、ある数の階乗を返す再帰的関数を書いてみよう。

階乗は，ある数とそれ以前のすべての整数の積を返す．たとえば，5の階乗は，5×4×3×2×1，つまり120である．

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

上記のプログラムでは、3の階乗である6という結果が得られます。最初は少し戸惑うかもしれません。プログラムを順を追って見ていけば、役に立つと思います。

1. この関数が呼ばれたとき、numberToMultiply は 3 になっています。
2. 条件が満たされないので、else 条件に移行する。
3. この関数は 3* を返しますが、その後一時停止します。この関数は自分自身を呼び出して、返される値の残りを決定する必要があります。
4. 今回、この関数が呼ばれたとき、numberToMultiply の値は 2 になっています。
5. 条件が満たされないので、else 条件に移行する。
6. この関数は 2* を返しますが、その後一時停止します。この関数は自分自身を呼び出して、返される値の残りを決定する必要があります。
7. この関数は再び呼び出され、今度は numberToMultiply の値が 1 に設定されます。
8. 条件を満たした場合、この関数は1を返します。
9. ステップ6の関数は、ステップ3の関数に2*1を返すことができるようになりました。
10. ステップ3の関数は、3*2*1、つまり6を返すことができるようになりました。

再帰は厄介な概念である。機能を重ねるという考え方が有効かもしれません。最終的に解析された関数は、すべての関数の応答が終了するまで、スタックに情報を送り返すことができます。

これは事実上、コンピュータが行っていることです。関数を呼び出すと、それが戻るまでメモリ上に残ります。つまり、再帰的な関数は、ループよりもはるかに多くのメモリを使用することができます。

そのため、ループを再帰的な関数として記述するのは非効率的かもしれませんが、ループの組み立てを練習するには良い方法です。ループを再帰的な関数としてコーディングしても、同様の結果が得られるはずです。

ループを再帰的関数に変換する例

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の基本的な例題

再帰的関数の実例

上の例は、再帰を使わない良い例である。では、再帰はどこで使われるのか？

データが2分木で構成されている場合、多くの経路でデータを検索する必要があります。ツリーの各ポイントで、右から探索を続けるか、左から探索を続けるかを決めなければなりません。ツリーのどの部分を訪れているかを変数に保存することもできるが、再帰的関数はその情報を自然に記録している。

上の木の中から数字の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 (left)は終了し、右側をチェックする。両側が選択されると、検索は枝分かれして後退し、右側のチェックを続ける。

アルゴリズムが木全体を探索する場合、以下の順序で進行する。

2、7、2、6、5、11、5、9、4

上の擬似コードで確認してみてください。

再帰性の概要

再帰は上級者向けのテーマです。理解するのに時間がかかり、コーディングがうまくできるようになるにはさらに時間がかかります。これは、再帰的な関数を一歩一歩たどる場合に役立ちます。各関数呼び出しの表現を学ぶ際には、関数をたどる際にインデックスカードを重ねたり、コメントを書き込んだりすると効果的でしょう。

再帰的な関数を書く場合、まず関数をどのように終了させるかを決定する。次に、ループをどのように設定するかを決めます。次の関数呼び出しに送るべき情報と返すべき情報を判断する。

再帰性を学ぶには、実践して失敗から学ぶのが一番です。あなたの古いコードを見て、ループを再帰関数として書き直すことに挑戦してみてください。これはコードの効率を上げるものではないかもしれませんが、良い習慣になるでしょう。