復帰(Recursion)

さいきかんすう

関数で自分を呼び出す方法で
同じ構造の問題を小さなブロックに分けることによって問題を解決する分割征服アルゴリズム.

いつ使いますか。

をより小さな問題ブロックに分割できる場合、

.

ネストされた重複文が多すぎたり、ネストされた回数が予測しにくい

さいきかんすうこうぞう

base case

recursive case

考え直す

の問題をどのように解決するかを考えています.

問題を区分する基準を決定し、基準に基づいて問題をより大きく、より小さく区分する.
入力値または問題の順序とサイズ
指定した入力値または問題のサイズを区別したり、問題の順序を明確に決定したりできる場合は、区別に役立ちます.

再回帰の基礎(Base case)

復帰の脱出条件(召喚を停止する条件)となる.
問題を区別し、最も解決しやすい問題から解決します.
基本的には、問題を再帰的に解決する必要はありません.

function fibonacci(n) {
  let arr = [0, 1];

  let fib = (n) => {
    if (arr[n] !== undefined) {
      return arr[n]; // 이미 있는 건 그대로 리턴 [0, 1]
    }
    arr[n] = fib(n - 1) + fib(n - 2);
    return arr[n];
  };

  return fib(n);
}

上記のコードは,ファボナッチ数列を求める再帰関数に注釈構造を適用する.
このとき,条件文により最小の問題が解決される.

if (arr[n] !== undefined) {
      return arr[n]; //이미 있는 건 그대로 리턴 [0, 1]
    }

再帰的な問題解決(Recursive Case)

fibonacciを救うため(5)
arr[5]==定義されていないため
fib(5-1)+fib(5-2)を求めなければなりません.

fib(5-1) + fib(5-2) === fib(4) + fib(3)
fib(4-1) + fib(4-2) === fib(3) + fib(2)
fib(3-1) + fib(3-2) === fib(2) + fib(1)
fib(2-1) + fib(2-2) === fib(1) + fib(0)
デバッガを回すと、callスタック上でfibが4回実行されているのが見えます.
順次
n=5時のfib
n=4時のfib
n=3の場合のfib
n=2の場合のfib
呼び戻される.

n=1の場合arr[n]!==未定義だから
[0,1]が呼び出されます.

arrにfib(n)で計算した値を追加します.
arr = [0, 1, 1, 2, 3, 5]
最終的にfib(5)、arr[5]の値5(戻る)が呼び出されます.
Return value: 5