再帰
動的計画法は、多周期ないし多段階の最適化問題を再帰形式で再記述する数理最適化へのアプローチ手法である。動的計画法の主な成果がベルマン方程式で、これは最適化問題の直近時(直近段階)での値を、その次回時刻(次段階)における値の観点から記述するものである。
ここではプログラミング手続きの観点から、再帰との主な違いを述べる。
回帰 - 元々あったオブジェクト(元の位置や状態)に戻ってくる事を指す。
対して「再帰」は元々のオブジェクトではなく、その参照 (計算機科学)にあたる小さいオブジェクトを呼び出す。
帰納 - 証明手続きの方向性として「基底段階の小さなものから段々と大きい(普遍的な)もの」へと進んでいく。特に数学的帰納法の帰納段階では、任意の自然数 k {\displaystyle k} に対して P ( k ) → P ( k + 1 ) {\displaystyle P(k)\to P(k+1)} が成り立つ事を示す。
対して「再帰」のプログラムは「大きなものから、段々と小さいもの」に進んでいく。 P ( k ) {\displaystyle P(k)} を計算するために k − 1 {\displaystyle k-1} の参照オブジェクトを呼び出し、この k {\displaystyle k} が基底段階に達するまで処理を繰り返し行う。
平行な合わせ鏡の間に物体を置くと、その像が鏡の中に無限に映し出される。このように、あるものが部分的にそれ自身で構成されていたり、それ自身によって定義されている時に、それを「再帰的(Recursive)」だという。論理的思考の重要な特質のひとつであり、数学では漸化式や数学的帰納法が再帰的構造を持っている。計算機科学だと、オブジェクト (プログラミング)やメソッド (計算機科学)のクラス (コンピュータ)が、以下2つの項目で定義できる場合に再帰的構造だと言える。
単純な基底段階 (base case) - 答えを出すのに再帰を使わない、論理展開の終着点。基底は複数あっても構わない。
再帰段階 (recursive step) - 後続のあらゆる事例を基底段階に帰着させる一連の法則。
例えば、これは人間の祖先の再帰的定義である。ある人物の祖先は次のいずれかになる。
その人物の親(基底段階)、または
その人物の親の祖先(再帰段階)。
フィボナッチ数列は、再帰を用いた古典的な数式例である。