재귀 함수

재귀란?

• 원래의 자리로 되돌아가거나 되돌아옴
• 재귀 함수는 js에선 같은 함수를 반복 한다. 즉 함수 안에서 자기 자신을 호출에 다시 함수를 호출 하는 것(반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다)

재귀로 문제 해결하기

1. 문제를 작게 쪼개기
2. 1번과 같은 방식으로, 문제가 더는 작아지지 않을 때까지,가장 작은 단위로 문제를 쪼갠다.
3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결한다.

함수가 작동하는 방식

• 위 그림처럼 밖에서 안으로 순차적으로 함수가 작동한다.

재귀는 언제 사용하는 게 좋을까?

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

• 모든 재귀 함수는 반복문으로 표현할 수 있다 하지만 재귀를 적용할 수 있는 대부분의 경우, 재귀를 적용해 코드가 더욱 간결하고 이해하기 쉽다.
• 재귀는 알고리즘 문제의 많은 부분을 차지 하기 때문에 기초를 확실하게 다져두는 게 좋다.

재귀적으로 사고하기

1. 재귀 함수의 입력값과 출력값 정의하기
   • 재귀적으로 사고하는 데에 가장 먼저 해야 할 일은 문제를 추상적 또는 단순하게 정의 하는 것이다. 함수의 입출력값을 정의하는 것은 첫 출발점이며, 재귀 함수를 통해 풀고자 하는 문제, 즉 도달하고자 하는 목표를 정의하는 데 도움이 된다.
2. 문제를 쪼개고 경우의 수를 나누기
   • 그 다음 주어진 문제를 어떻게 쪼갤 것인지 고민 한다. 문제를 쪼갤 기준을 정하고 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분 할 수 있다. 일반적으론 입력값 기준으로 정하며 이때 중요한 포인트는 입력값이나 문제의 순서와 크기이다. 주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나 순서를 명확하게 정하게 되면 문제를 구분하는데 도움이 된다.
3. 단순한 문제 해결하기
   • 문제를 여러 경우로 구분한 후, 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초(base case)라고 부르며, 재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성하게 된다.
   • 탈출 조건이 없을시 재귀 함수는 끝없이 자기 자신을 호출하게 된다. 그만큼 문제를 최대한 작게 쪼갠 후에 문제를 해결하는 것이 중요하다.
4. 복잡한 문제 해결하기
   • 남아있는 복잡한 경우를 해결한다.
5. 코드 구현하기

	function recursive(input1, input2, ...) {
  // base case : 문제를 더 이상 쪼갤 수 없는 경우
 	 if (문제를 더 이상 쪼갤 수 없을 경우) {
   	 return 단순한 문제의 해답;
	  }

	  // recursive case : 그렇지 않은 경우
	  return 더 작은 문제로 새롭게 정의된 문제
    }