再帰を決して使わないのに、なぜ再帰を学ぶ必要があるのでしょうか? 再帰的なソリューションは、いくつかの考え方を訓練します。 1. 解決策を生成しようとするのではなく、「有効な解決策の構造は何か」を逆算して作業することから始めることがよくあります。一部の問題については、逆算する方がはるかに簡単です。 2. 問題を解決しているとき、すべての「もしも」に気を取られがちです。問題を再帰的に解決する場合、問題の 90% を「無視」し、1 つの部分だけを正しく理解することに集中することを余儀なくされることがよくありました。 3.命令型解ではしばしば「コーナー」ケースになるものは、再帰的なオンでは「基本ケース」です。再帰的に考えると、コーナーケースを無視しないように強制されることがあります。さらに、再帰的なソリューションではパターン マッチングが多用されるため、遭遇する可能性のあるすべての状況を考える必要があります。 ここに本当に良い例があります:Leetcode 335 Self Crossing(難しい問題)。 グリッド上のらせん状の軌道をたどって移動します(つまり、北、南、東、または西にある程度の距離を移動した後、常に左折します)。問題は、「らせんの各「セグメント」の距離を順番に与えられた場合、らせんはそれ自体を交差したかどうかです。」 これに対する解決策は、それ自体を呼び出す関数である必要はありませんが、「良い」解決策は再帰的なプロパティを使用します。 1. まだ交差点を見つけていない場合は、過去に交差点や無効なスパイラルは存在しなかったと想定できます。さらに、左に曲がることしかできないため、左、右、上、下のいずれを走行しても問題ではないことに気づきます。私たちが気にするのは、前のセグメントが前のターンと平行であるかどうか、そしてそれらがどれだけ離れているかだけです。 2. 左に曲がると、スパイラルに衝突できる「セグメント」の数は非常に限られていますが、これはスパイラルがどれほど大きくなっても「再帰的に」当てはまります。スパイラルについては、無視できる過去のデータがたくさんあります。 3. 前のターンで、あなたのロジックに影響を与えるシナリオの数は限られています: a) 何も衝突しないほど遠くまで移動したか、b) そうでない場合、衝突する可能性のあるものは何ですか?(これも制限されています)。 Leetcode ハードの厄介な点は、重要な洞察を見つけると突然簡単になることです。しかし、これらの重要な洞察は、再帰的プログラミングの訓練を受けていれば、より自然に得られるでしょう。 それは、自分自身を呼び出す関数を設計することだけではなく、自分自身を呼び出す関数で解決できるように問題を分解することを強制することです。問題を分解する方法が多ければ多いほど、「アハ」解決策が見つかる可能性が高くなります。 もちろん、私の職業では leetcode する必要はありませんが、問題を理解できるように分解する創造的な方法を見つける必要があり、再帰のトレーニングは間違いなくそれに役立ちました。