18. 재귀(Recursion)

쪼개서 생각하는 습관 기르기

문제: 자연수의 리스트를 입력으로 받아 리스트의 합을 리턴하는 함수 'arrSum'을 구하라

보통, 지금까지는 새 변수를 만들어 0으로 할당하고, for문을 이용해 0번째 인덱스부터 마지막 인덱스를 그 변수에 더해주는 방법으로 구했다. 하지만 얼마전에 배운 reduce를 이용한 고차함수 사용이 가능할 것 같다.

how? 직접 해보기!!!

function arrSum(arr) {
 return arr.reduce(function (acc, cur) {
   return acc + cur;
 }, 0);
}

재귀 vs. 고차함수

다른점..?

 

재귀는 언제 사용하는게 좋을까? (사용시점을 판단하는 기준)

1. 주어진 문제가 (구조는 비슷하고) 더 작은 문제로 나뉘어 질 수 있는 경우: 어제 풀었던 nestedArray의 경우를 말하는듯!

2. "중첩"된 루프가 ㅁ낳거나 중첩의 정도(number of loops)를 미리 알 수 없는 경우: 이것도 nestedArray!

 

재귀는 보통 while/for문으로도 해결이 가능한 문제지만, 재귀를 사용한다면 보통 코드가 더 간결하고, 이해하기 더 쉬워진다.

하노이의 탑과 조합 문제로 비교해보기!!

 

재귀적 사고 연습하기

1. 재귀 함수의 입력값과 출력값 정의하기

input과 output으로 받는 값의 "타입"을 정리한다고 봐도 좋을듯

 

2. 문제를 쪼개고 경우의 수를 나누기

주어진 문제를 어떻게 쪼갤 것인지 고민할 때 일반적으로 입력값이 그 기준을 정하는 대상이 된다. 이 때 중요한점은 순서와 크기다.

위의 문제로 예를 들면, arrSum은 입력값이 되는 배열의 크기(length)에 따라 구분 할 수 있겠다. 그리고 이 크기가 변해도 구하는 방법은 동일하다면, 문제를 잘 구분했다고 볼 수 있다.

 

3. 단순한 문제 해결하기

재귀의 기초(base case)는 여러 경우로 구분한 문제 중 쉬운 문제부터 해결하는 것을 의미한다. 재귀의 기초는 재귀 함수 구현 시 재귀의 탈출 조건(재귀 호출을 멈추는 조건)을 구성하게 된다.

input으로 받는 배열이 빈배열일 때, 배열을? arrSum을? 더 이상 쪼갤 수 없고, arrSum은 0이 된다.

 

4. 복잡한 문제 해결하기

남아있는 진짜 문제들을 해결한다.

길이가 1 이상인 배열을 입력으로 받는 경우를 보자. 맨 앞의 요소와 나머지 배열(결국 이 배열이 빈 배열이 될 때 까지)을 새로운 입력값으로 갖는 문제를 해결하는 방식이다. 이 때 맨 앞의 요소를 head라 이름 붙이고, 남아있는 배열을 tail이라 한다.

 

5. 코드 구현하기

코드 써보기!

 

Solving factorial problem with recursion

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

5! = 5 * 4!

5! = 5 * 4 * 3!

...

function fac(n) {
  if(n === 1) {
    return 1;
  }
  else {
    return n * fac(n - 1)
  }
}

fac(n)함수는 위와 비슷한 방식으로 진행되는 것을 볼 수 있다.

fac(5) => return 5 * fac(4) => return 5 * 4 * fac(3) => return 5 * 4 * 3 * fac(2) => return 5 * 4 * 3 * 2 * fac(1) => return 5 * 4 * 3 * 2 * 1이 되겠다. if 문에서  fac(1) = 1이라고 해줬기때문에 가능한 것. 결국 fac(1)을 만날 때까지 fac(n)이 계속 실행되는 것.

어떤 함수 안에서 자기 스스로를 호출하는 과정을 재귀라고 함. fac(5)는 (함수)자기 자신, fac(n) 총 5번 불렀다.