[JS] 재귀

Recursion

함수 안에서 다른 함수를 호출해야할 때, 함수가 자기 자신을 호출하는 경우가 있다. 이를 재귀라고 부른다.

• 주어진 문제가 (구조가 비슷하고) 더 작은 문제로 나눌 수 있는 경우
• 중첩된 루프가 많거나, 얼마나 중첩해야할 지 미리 알 수 없는 경우

1) 재귀로 factorial 구하기

5! => 5x4x3x2x1

재귀 : 어떤 함수가 안에서 자기자신(함수)를 또 불러내는 것

function factorial(n) {
  // base case
  if(n === 1) {
    return 1;
  }
  // recursive case
  return n * factorial(n - 1);
}

2) 재귀로 Fibonacci 풀기

// 피보나치 수열의 num 번째 요소 리턴하기
function fibonacci(num) {
// base case
  if (num <= 1) { // num은 0 이상의 정수
    return num;
  }
// recursive case
  return fibonacci(num - 1) + fibonacci(num - 2);
}