JavaScript의 재귀

재귀란 무엇입니까?

재귀 함수는 호출되지 않을 때까지 자신을 호출하는 함수입니다. 그리고 이 기술을 재귀라고 합니다.

통사론

const recurse = () => {
    recurse();
}

recurse();

이 재귀 함수는 자신을 영원히 호출하므로 조금 더 손봐야 합니다.

const recurse = () => {
  if (condition) {
    recurse();
  }
  // stop calling recurse()
};

recurse();

이 함수는 조건을 충족하면 계속 자신을 호출하고 그렇지 않으면 실행을 중지합니다.

예

1- 간단한 예

const countDown = (start, end) => {
  console.log(start);
  if (start > end) {
    countDown(start - 1, end);
  }
};

countDown(19, 7); // 19 18 17 16

무대 뒤에서

countDown(19, 7)은 19를 인쇄하고 countDown(18, 7)을 호출합니다.

countDown(18, 7)은 18을 인쇄하고 countDown(17, 7)을 호출합니다.

countDown(17, 7)은 17을 인쇄하고 countDown(16, 7)을 호출합니다

.

countDown(16, 7)은 16을 인쇄하고 실행을 중지합니다.

2- 계승

0! = 1

1! = 1

2! = 2 * 1

3! = 3 * 2 * 1

4! = 4 * 3 * 2 * 1

5! = 5 * 4 * 3 * 2 * 1

const factorial = (num) => (num < 0 ? -1 : num === 0 ? 1 : num * factorial(num - 1));

console.log(factorial(5)); // 120

무대 뒤에서

계승(5) = 5 * 계승(4)

계승(4) = 4 * 계승(3)

계승(3) = 3 * 계승(2)

계승(2) = 2 * 계승(1)

계승(1) = 1 * 계승(0)

계승(0) = 1

3- 피보나치

피보나치 수열은 다음과 같이 작성됩니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, ...

피보나치 수열은 처음 두 항이 0과 1인 정수 수열입니다. 그 후 다음 항은 이전 두 항의 합으로 정의됩니다. 따라서 n번째 항은 (n-1)번째 항과 (n-2)번째 항의 합입니다.

다음은 재귀를 사용하여 주어진 인덱스에서 피보나치 값을 반환하는 코드입니다.

const fibonacci = (n) => (n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2));

console.log(fibonacci(5)); // 5

무대 뒤에서

피보나치(5) = 피보나치(4) + 피보나치(3)

피보나치(4) = 피보나치(3) + 피보나치(2)

피보나치(3) = 피보나치(2) + 피보나치(1)

피보나치(2) = 피보나치(1) + 피보나치(0)

피보나치(1) = 1

피보나치(0) = 0