Recursion - tanakakenji/Rinko GitHub Wiki

はじめに

再帰とは、計算問題を解決する手法の一つで、その解決策がより小さな同一問題のインスタンスの解に依存するものです。

すべての再帰関数は、以下の2つの部分を含んでいます。

• ベースケース（または複数のケース）の定義：これは、再帰が停止する条件を定めます。そうしないと、無限に続いてしまいます！
• 問題をより小さなサブ問題に分割し、再帰呼び出しを呼び出すこと

再帰の最も一般的な例の1つは、フィボナッチ数列です。

• ベースケース: fib(0) = 0 および fib(1) = 1
• 再帰関係: fib(i) = fib(i-1) + fib(i-2)

def fib(n):
  if n <= 1:
    return n
  return fib(n - 1) + fib(n - 2)

コーディング面接に関連する多くのアルゴリズムは、再帰を多用しています - 二分探索、マージソート、木構造の走査、深さ優先探索など。この記事では、再帰を使用するものの、他のよく知られたアルゴリズムの一部ではない質問に焦点を当てます。

学習リソース

• 参考資料
  • Recursion, University of Utah
• 動画
  • Tail Recursion, University of Washington

面接中に注意すべきこと

• 常に、再帰が終了するようにベースケースを定義することを忘れないでください。
• 再帰は、順列やすべての組み合わせを生成する木構造の問題に役立ちます。シーケンスのすべての順列を生成する方法と、重複を処理する方法を知っておく必要があります。
• 再帰は暗黙的にスタックを使用します。したがって、すべての再帰的なアプローチは、スタックを使用して反復的に書き換えることができます。再帰のレベルが深くなりすぎてスタックオーバーフローを引き起こす場合に注意してください（Pythonのデフォルトの制限は1000です）。面接官にこの点を指摘すると、ボーナスポイントが得られるかもしれません。再帰にはスタックが関与するため、テールコール最適化（TCO）がない限り、空間計算量がO(1)になることはありません。選択した言語がTCOをサポートしているかどうかを確認してください。
• ベースケースの数 - 上記のフィボナッチの例では、再帰呼び出しの1つが fib(n - 2) を呼び出すことに注意してください。これは、コードが入力範囲内の関数のすべての可能な呼び出しをカバーするように、2つのベースケースを定義する必要があることを示しています。再帰関数が fn(n - 1) のみを呼び出す場合、必要なベースケースは1つだけです。
• コーナーケース
  • n = 0
  • n = 1
  • 再帰関数のすべての可能な呼び出しをカバーするのに十分なベースケースがあることを確認してください。

テクニック

• メモ化
  • 場合によっては、以前に計算された入力の結果を計算していることがあります。もう一度フィボナッチの例を見てみましょう。fib(5) は fib(4) と fib(3) を呼び出し、fib(4) は fib(3) と fib(2) を呼び出します。fib(3) は2回呼び出されています！ fib(3) の値がメモ化されて再利用されると、アルゴリズムの効率が大幅に向上し、時間計算量は O(n) になります。

必須の質問

これらは、このトピックを学習していて、必須の質問を練習した場合に練習すべき重要な質問です。

• Generate Parentheses
• Combinations
• Subsets

推奨される練習問題

これらは、このトピックを学習し、必須の質問を練習した後に練習することをお勧めする質問です。

• Letter Combinations of a Phone Number
• Subsets II
• Permutations
• Sudoku Solver
• Strobogrammatic Number II (LeetCode Premium)