再帰的アルゴリズムについて詳しく解説

導入

再帰アルゴリズムと再帰関数は、コンピューター サイエンスの基礎です。アルゴリズムがそれ自体を呼び出す場合、そのアルゴリズムは再帰的であると言われます。

再帰を導入した最初のプログラミング言語はLISPと Algol 60 で、現在ではすべての最新のプログラミング言語が再帰の実装を提供しています。

一般に、再帰的アルゴリズムは、アルゴリズム自体を明示的に呼び出したり呼び出したりせずに実行される、いわゆる命令型アルゴリズムまたは反復アルゴリズムと対比されます。

予備的な例

モリエールの『Le Bourgeois gentilhomme (第 2 幕第 4 場)』の例から始めましょう。主人公のムッシュ・ジュルダンは、メモを書くための「勇敢な」方法をすべて知りたいと考えています。 「美しいマーキス、あなたの美しい目、愛で私を死なせてください」というフレーズから、彼はあなたの美しい目、美しいマーキス、愛で私を死なせ、それからあなたの美しい目、私を死なせて、美しいマーキス、愛で、そしてあなたの美しいを描くことができました目は愛で私を死に至らしめる、美しい侯爵夫人など。

ムッシュ・ジュルダンは、これらすべての順列をどのように生成していくべきでしょうか?確実にそこに到達する最善の方法は、再帰的なプロセスを使用することです。その 1 つは次のとおりですが、読者は他のものを想像することができます。まず第一に、あなたの美しい目 — 私を死なせてください — 愛の文のすべての順列を構築します。次に、これらの順列で、最初の位置に、次に 2 番目の位置に、次に 3 番目の位置に、そして 4 番目の位置にbelle Marquiseという文を挿入します。アルゴリズムはそれ自体を呼び出すため再帰的です。実際、美しい侯爵夫人 — あなたの美しい目 — 私を死なせる — 愛のすべての順列を構築するには、あなたの美しい目 — 私を死なせる — 愛のすべての順列を構築する必要があります。さらに、このアルゴリズムは確かに一般的なアルゴリズムです。なぜなら、ムッシュ・ジュルダンが自分の詩的な側面を改善したいと考え、彼の哲学の師匠が彼に言ったように、 「ベル・マルキーズ – あなたの美しい目 – 私が作る」というフレーズのすべての順列を構築したいと思うからです。 – 死ね — 愛で、これには 5 つの構成要素があります。彼は同じ方法で、もう一度同じ方法で文を進めます。美しい侯爵夫人 — あなたの美しい目 — 私を愛で — 死なせてください — あなたのために、6つの構成要素があります。

別の例: 最大 q 個の和への自然数の分解の数

再帰的アプローチが必要な数学のケースを考えてみましょう (記事「整数の共有関数」を参照)。

• 例:

和は、数値を自然数の和に分解するときに合計に入る正の自然数です。したがって、5 の分解数をd (5,3)と書くと、5 を最大 3 つの合計に分解することは、5、4+1、3+2、3+1+1、2+2+1 となります。合計が最大 3 つであれば、 d (5,3) = 5となり、 5 を正確に3 つの合計に分解する数をd ‘(5,3)と書くと、 d ‘(5,3) = 2 になります。これらの分解は 3+1+1 と 2+2+1 です。

• 変性したケース:

p = 0の場合、0 は最大 q 個の和、つまり和を含まない和への分解のみを持ちます。したがって、 d (0, q ) = 1となります。厳密に正の p は最大でもゼロ和に分解されないため、 d ( p + 1.0) = 0 となります。 p < qの場合、p を正確に q 個の合計に分解することはありません。したがって、p を最大 q 個の合計に分解する回数は、p を最大 p 個の合計に分解する回数になります。これは、次のように記述されます。 d ( p , q )= d ( p , p ) 。

• 一般的なケース:

p を最大q 個の合計に分解する回数は、p を正確にq 個の合計に分解する回数に、p を最大q-1 個の合計に分解する回数を加えたものであることが簡単にわかります。それで

• d ( p , q ) = d ‘( p , q ) + d ( p , q − 1) 。

ここで、pa が正確に q の合計である場合、これはこれらの合計がすべて厳密に正であることを意味します。したがって、これらの合計のそれぞれから 1 を減算すると、p – q を最大 q 個の合計に分解した Or が得られます。 :

• d ‘( p , q ) = d ( p − q , q )

そして最後に

• d ( p , q ) = d ( p − q , q ) + d ( p , q −1) 。

言い換えれば、もし$$ {p\ge q} $$