[JS] 재귀 - 하

하

 

1. sumTo

 

• 먼저 base case, recursive  case를 생각하자.

 

---

 

2. factorial

 

 

---

 

3. fibonacci

 

• 메모리제이션은 금지된다. 

 

• 그림으로 살펴보면 금방 이해가 된다.

// 🟣 반복문일 때

function fibonacci(num) {
  // 피보나치를 한 마디로?
  // 다음 수 = 맨 끝에 있는 수 + 그 앞에 있는 수
  // 1. 피보나치 수열을 넣어줄 배열을 만든다.
  let fib = [];
  // 2. 반복문을 돌린다. -> 0부터 num까지 반복
    // 0과 1은 피보나치수열의 기본세팅
    // i가 0일 때, 1일 때는 바로 배열에 push한다.
  for (let i = 0; i <= num; i++) {
    if (i === 0 || i === 1) {
      fib.push(i) // [0, 1]
    } else {
      // 3. 다음 수 = 맨 끝에 있는 수 + 그 앞에 있는 수
      // 반복문의 현재 시점: i = 2, fib = [0, 1]
      // 2번째 요소를 구하기 위해 1번째 요소와 0번째 요소를 더한다. -> fib[2] = fib[1] + fib[0]
      // 다음 반복
      // i = 3, fib = [0, 1, 1]..
      // fib[3] = fib[2] + fib[1]...
      // 그 다음 반복...
      // i = 4, fib = [0, 1, 1, 2]..
      // fib[4] = fib[3] + fib[2]...
      // 이 과정을 i를 이용하여 표현해 보자.
      // fib[i] = fib[i - 1] + fib[i - 2] -> 이렇게 해도 답이 나온다.
      fib.push(fib[i - 2] + fib[i - 1]);
    }
  }
  // 4. 반복이 끝난 후 fib를 리턴
  return fib;
}

 

---

 

4. arrSum

 

function arrSum (arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length === 0) {
    return 0
  }

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr.shift() + arrSum(arr)
}

 

---

 

5. arrLength

 

 

---

 

6. drop