재귀함수(recursion)

재귀 : 원래의 자리로 되돌아가거나 되돌아옴

재귀 함수란?

자기 자신을 호출(리턴)하는 형태의 함수다. 반복되는 형태라는 점에서 반복문 (For, Whlie) 과 같다고 할 수 있다.

재귀적 사고

어떤 문제를 해결할 때, 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법을 재귀적 사고(recursion)라고 한다.

1. 원래의 문제에서 출발하여 더 작은 경우를 생각
2. 계속해서 문제가 더는 작아지지 않을 때까지 더 작은 경우를 생각
   1) 문제를 더이상 쪼갤 수 없을 때
   2) 마지막 문제에 도달했을 때
   3) 탈출 조건을 생각하자
3. 이렇게 문제 풀기를 미루다가, 문제가 간단해져서 바로 풀 수 있게 되는 순간에 미뤄왔던 문제들을 차근차근 해결

결국

반복적으로 사용하는 부분을 재귀함수로 나타내는 방법을 배워야 한다. 하지만 무한으로 반복을 하는 게 아니니까 탈출 조건을 명시해줘야 한다.
1. Base case 언제 탈출할 것인가?
이는 즉 언제 답을 찾을 거냐는 말과 같고 여기서 무슨 답이냐고 묻는다면 더이상 쪼갤 수 없는 문제의 답이다.
2. Recursive case 지금 문제를 쪼갤 수 있는가?
recursive case를 생각하다 보면 base case도 생각나기 마련이다.

탈출 조건

수(num)를 입력받아 1부터 num까지의 합을 리턴

• num이 5라면

1. 5+4+3+2+1 은
2. 5+(4+3+2+1)와 같다
3. 같은 의미로 5+4+(3+2+1)과도 같다
4. ...

위 문제를 재귀적 사고 를 통해 코드로 작성

sumTo(5) = 5+sumTo(4) //15
	     sumTo(4) = 4+sumTo(3) //10
			  sumTo(3) = 3+sumTo(2) //6
				       sumTo(2) = 2+sumTo(1) //3
						     sumTo(1) = 1

function sumTo(num) {
  if(num===0) { //탈출 조건
    return 0
  }
  return num + sumTo(num-1)
}

여기서 탈출 조건이 없다면 끝없는 반복을 거치다가 결국 MAXIMUM CALL STACK 이란 결과를 나타낼 것이다. 재귀 함수는 반복문과 같이 탈출 조건을 반드시 명시해줘야 한다.

재귀 함수 템플릿

function recursive(input1, input2, ...) {
  // 재귀의 기초 (base case)
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}