前置き
この記事は1つのトピックについてのみ書かれており、再帰について書かれたほとんどすべてのアルゴリズム本の最初のトピックですが、それについて話すことに努め、異なるものを提供するために4つの異なる視点をここで共有しています。
アルゴリズム思考
メソッドが自分自身を呼び出すことが再帰的であることは誰でも知っています。
では、再帰とは？
A: 再帰の本質は、大きな問題をそれよりも小さな問題に分解する能力であり、小さな問題の解決策を持っていれば、小さな問題の解決策を使って大きな問題の解決策を構築することができます。
そのトリビアの解答はどのようにして得られたのですか？
A: 一回り小さい問題の解から構成されるのは、問題がゼロになるときの基本ケースです。
再帰的なゼロの問題だけでなく、再帰の終わりは、その問題の最小に移動し、直接結果を与えることができる、ダウンする必要はありませんが、そうでなければ、それはデッドループになります；
問題の各レイヤーは前のレイヤーよりも小さくなければならず、大きなケースから小さなケース、そして基本ケースへと移行するために、常に問題のサイズを小さくしていきます；
小さな問題に対する解を得た後、大きな問題に対する解をどのように構築できるかを知ることも重要です。
ですから、すべての再帰の問題で、これらの3つのステップに従って分析し、3つの問題を正解すれば、コードは簡単に書けるようになります。
フィボナッチ数列
ありきたりの質問ですが、ここでお話ししたことがきっと何かを与えてくれると思います。
説明
フィボナッチ数列は、ウサギの繁殖過程を研究する以外にすることがなかったイタリアの数学者が、それが次のような数列として書けることに気づいたものです：1、1、2、3、5、8、13、21...つまり、それぞれの数は最初の2つの数の和に等しい。つまり、それぞれの数は最初の2つの数の和に等しいのです。ですから、n番目の数が与えられたら、F(n)が何であるかを尋ねてください。
解析
数式で表すのは簡単です：
コードもシンプルで、先ほどまとめた3つのステップを使います：
じゃあ、それを書き出すのは
class Solution { public int fib(int N) { if (N == 0) { return 0; } else if (N == 1) { return 1; } return fib(N-1) + fib(N-2); }}
しかし、このリートコードの解は、経験的に答えより15％しか速くありません！
プロセス分析
つまり、再帰のプロセスを分析する方法についてです。
まずこの再帰木を描きます。例えばF(5)の再帰木です：
また、実際の実施ルートは？
まず、一番左の線に沿ってずっと、F(5)→F(4)→F(3)→F(2)→F(1)と、まあ最終的にF(1)=1に戻せるベースケースがあり、F(2)にこのレベルで戻り、F(0)まで下がり、底を打ってF(2)に戻り、F(2)=1+0=1の結果を得て、その結果をF(3)に戻し、F(1)に戻り、その結果を得てF(3)に戻り、F(3)=左+右=2を得て、その結果を上に戻し......。(3)、次にF(1)、結果を得てF(3)に戻り、F(3) = 左 + 右 = 2、そしてその結果を上に返す...
F(3)とF(4)を一緒にすることはもうできませんから、まずF(4)を実行し、それからF(3)に進まなければなりません。
IDEでデバッグすると、スタック内部で何が起こっているかがわかります。確かに、一番左の行が最初に取得され、全部で5つのレベルがあり、それから1レベルずつ上に戻っていきます。
わからない場合は、ビデオを見てください。
時間複雑性解析
アルゴリズムの良さはどのように評価するのですか？
結局のところ、すべての道はローマに通じているのです。しかし、それぞれの方法の長所と短所をどのように評価するかが、一般的に複雑さを測るのに使われます。
時間の複雑さ：独立変数が大きくなるにつれて、アルゴリズムに必要な時間がどのように長くなるか。
ここで大きなOは、最も懸念している状況でのアルゴリズムの性能を示し、それ以外のシステムは、春のラッシュチケットのときに保持することはできません、あなたはこのアルゴリズムが非常に優れていることを私に教えて？
もちろん、時間と空間を測る方法は他にもあります。
θ：タイトバウンドを表します。
Omega(n)：これは最良の場合、最良の場合を表します。
では、この質問の時間的複雑性は？
A: 各ノードを通過するため、合計時間となります。
ここで、各ノードで行われるのは、O(1)演算である合計と和算だけで、時間は各ノードで同じです：
合計時間 = ノード数 * ノードあたりの時間
そうすると、ノードの数を求める数学の問題になります：
N = 5では
最上位のレイヤー1ノード
2番目のレイヤー2ノード。
第3層に4ノード。
第4層に8ノード。
第5層は16ノードなので、これを埋めるととても大きなツリーになります :)
未充填の領域については心配しないでください。数ノードの差はあるはずですが、大きなO式の時間的複雑さは、申し上げたように最悪のケースです。
ノードの総数は
1 + 2 + 4 + 8 + 16
これはアイソペリメトリック級数の合計です。もちろん、数学の公式を使って計算することもできますが、素早く計算するためのもう一つのちょっとしたコツがあります：
実際には、各レイヤーのノード数は最後のレイヤーのノード数を超えないので、ノードの総数は最大でも最後のレイヤーのノード数*2になります：
最終層のノード数：2^n
空間複雑性解析
空間の複雑さは、一般的に本ではこう書かれています：
アルゴリズム動作時に必要なメモリ容量
アルゴリズムの実行に必要な容量。
この違いの例として、結果が長さnの配列を出力させる場合、このO(n)空間はアルゴリズムの空間複雑性にカウントされません。
空間の複雑さはどのように分析するのですか？
ちょうどフォンノイマンシステムについて話しました、図からも簡単にわかりますが、このルートの最も左は、最もスタックスペースを占有し、常にスタックを押している、つまり、5から4から3から2に押されている1に、唯一の各ノードの空間複雑さを占めるO（1）に戻るには、基本的なケースにされているので、合計空間複雑さはO（n）です。
上のビデオでも紹介しました知らない人は、上にスクロールしてビデオを見てくださいoh～！
最適化アルゴリズム
では、なぜこんな単純な操作に指数関数的な複雑な時間がかかるのでしょうか？一体なぜこんなに時間がかかるのでしょう？
この再帰ツリーでは、ダブルカウントが多すぎるということは、難しいことではありません。
例えば、ここでF(2)が3回計算され、F(3)が2回計算され、そのたびに計算し直さなければならないのは、熊が棒を折るようなものではなく、本当に苦い涙です。
そして、原因を突き止めたコンピュータは、この繰り返し計算を解決するために、実は人間と同じ方法、つまりメモを取るという方法を使うのです。
医師、弁護士、エンジニアなど多くの職業において、年齢が上がるほど経験の価値が高まるのはなぜでしょうか。彼らは蓄積の多くを見ているため、次に同じような問題に遭遇したとき、彼らはすぐに解決策を与えることができ、それらが解決できない場合でも、また、いくつかの盲目の試行錯誤を避けるために、過去の継続的な進歩の高さに立つのではなく、毎回ゼロから開始します。
最適化アルゴリズムの話に戻りますが、コンピューターはどうやってメモを取っているのですか？
F(n)を求めるのは、F(0)～F(n-1)の値を記録するのと同じくらい簡単です。
F(0)～F(n-1)の値を記録します。
あとは、それを保存するのに適当なデータ構造を選ぶだけです。
それなら、HashMap使うか、配列を使って格納すればいいのは明らかです：
| F(n) | 0 | 1 | 1 | 2 | 3 | 5 |
そしてこのカンニングペーパーを使えば、前から後ろまで結果を得ることができ、各ポイントは一度しかカウントされません。
= ノード数 * ノードあたりの時間100％です。
しかし、ご覧の通り、スペースを最適化する余地はあるはずです。
考えてみれば、ノートを取るとき、そんなにたくさんのノートをつける必要があるのでしょうか？幼稚園、小学校、中学校、高校とノートをつける必要があるのでしょうか？
それなら、各項の計算はその前の2項だけに依存しますから、その2項だけを残しておけばいいのです。
その場合、長さ2の配列を使って計算するか、2つの変数を使うだけです。
コードを更新してください：
class Solution { public int fib(int N) { if (N == 0) { return 0; } if (N== 1) { return 1; } int[] notes = new int[N+1]; notes[0] = 0; notes[1] = 1; for(int i = 2; i <= N; i++) { notes[i] = notes[i-1] + notes[i-2]; } return notes[N]; }}
これにより、空間の複雑さはO(1)に最適化され、時間の複雑さはレコードの配列と同様にO(n)となります。
このアプローチは動的プログラミングDynamic Programmingであり、書かれたコードは非常にシンプルです。
次にリカージョンとDPを比較してください：
それは大から小へ、層ごとに分解し、基本ケースの分解がアップの組み合わせに戻ることができなくなるまでです；
小から大へ、しっかりメモを取り、前進し続けることです。
つまり
このメモをどう記録するか、どう効率よくメモを取るかがDPの難しいところです。
再帰を使って問題を解く場合、スタック上の空間はO(n)であることがわかりますが、DPを使えば空間をO(1)に最適化することができます。
実際、フィボナッチ数列は実生活に多くの応用があります。
例えば、私たちの会社や多くの大企業では、各タスクに点数を付けます。1点というのは、完了するのに約1日かかるという意味で、点数は1、2、3、5、8の5種類しかありません。
タスクは終わらないし、皆の時間は限られているので、毎回グループミーティングを行い、皆にとって最も重要なタスクをピックアップします。
羊の皮を被った狼
答えてください：
ただ、もうそんなぶっきらぼうな言い方はできません。
例えば、とても有名な質問です：
N段の階段は、一度に1段か2段移動することができます。
この質問をこう考えてみてください：
現在の位置に立っているのは、前の階か、前の2階からしか来られないので、f(n)=f(n-1)+f(n-2)。
class Solution { public int fib(int N) { int a = 0; int b = 1; if(N == 0) { return a; } if(N == 1) { return b; } for(int i = 2; i <= N; i++) { int tmp = a + b; a = b; b = tmp; } return b; }}
再帰は時間がかかりすぎるので、forループバージョンを書きました。
f = lambda n: 1 if n in (1, 2) else f(n-1) + f(n-2)
そしてキャッシングの方法です。
def fib(n) a, b = 1, 1 for i in range(n-1): a, b = b, a+b return a
末尾再帰 末尾再帰：つまり、再帰はメソッド全体の最後の文です。
では、これのどこが特別なのでしょうか？
もちろん、賢いコンパイラーは自動的にそれを行います。
それはなぜですか？
戻るときにバックトラックする必要がないため、ここでの再帰は最後のステップであり、前のレベルに値を戻す必要はありません。
def cache(f): memo = {} def helper(x): if x not in memo: memo[x] = f(x) return memo[x] return helper@cachedef fibR(n): if n==1 or n==2: return 1 return fibR(n-1) + fibR(n-2)
def fib(n, a=0, b=1): if n==0: return a if n==1: return b return fib(n-1, b, a+b)
