재귀함수

재귀?

재귀(recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. 순환정의 또는 재귀적 정의라고도 한다. -위키백과-

재귀 함수란?

어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수로서 정의 단계에서 자신을 재참조하는 함수다. 자신을 호출한 후 끝날때까지 함수 호출 이후의 명령문이 수행되지않는 점은 반복문과 동일 하다. 재귀함수는 종료 조건이 꼭 포함되어야 무한 루프를 방지할 수 있다. 반복문을 사용한 코드는 재귀함수를 통해 구현이 가능하다. 반대로 모든 재귀함수는 반복문으로 표현이 가능하다.

재귀적 사고

1. 재귀함수의 입력값과 출력값을 정의한다
   문제를 가장 추상적으로 또는 가장 단순하게 정의하기 위해 문제를 더 가장 작은 단위까지 나눠 본다.
2. 문제를 쪼개고 경우의 수를 나누기
   기준을 전하고 문재를 쪼갠다. 일반적으로 입력값을 기준으로 정하며, 이때 중요한 관점은 입력값이나 문제의 순서와 크기이다. 그리고 문제에 주어진 입력값에 따라 경우의 수를 나눈다. 보통 문제를 더 이상 쪼갤수 있는경우와 그렇지 않은 경우로 나눈다.
3. 단순한 문제 해결하기
   문제의 경우의 수중 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초(Base case)라고 부른다. 재귀의 기초는 후에 재귀함수를 구현할 때, 재귀의 탈출 조건을 구성한다.
4. 복잡한 문제 해결하기
   남아있는 복잡한 문제를 해결한다. 고정값과 변화하는 값만 재대로 정의할 수 있다면 재귀함수를 구현 할 수 있다.

재귀함수 적용

반복문 코드 -> 재귀함수로 변환

// 반목문
function inOrderNumber(num) {
  let result = '';
  for (let i = 1; i <= num; i += 1) {
    result = result + i;
  }
  return result;
}

const result = inOrderNumber(7);
console.log(result); // > 1234567

// 재귀함수
function recursionInOrderNumber(num) {
  if (String(num).length === num) {  //base case, 조건 충족시 재귀탈출!
    return num;
  }
  return recursionInOrderNumber(num - 1) + `${num}`;
}

const resultRecursion = recursionInOrderNumber(7);
console.log(resultRecursion); // > 1234567