재귀함수(recursion)

정의 단계에서 자신을 참조하는 함수를 재귀함수라 한다.
전달되는 매개변수만 달라질 뿐 같은 로직을 반복하는 함수이다.
큰 문제에서 작은 부분문제로 나눠서 풀 때 사용한다.
목표 작업을 변형한 작업으로 단순화 시킬 수 있을 때도 재귀를 사용할 수 있다.

자기 자신을 호출하는 함수, 재귀함수 !

재귀함수는 함수 종료 조건이 반드시 있어야 한다.
종료 조건이 없으면 무한하게 반복되기 때문이다.
알고리즘 문제를 풀 때는 재귀함수 또는 반복문으로 풀 수 있는 문제가 있다면 반복문을 사용하는 것이 좋다. (문제에 따라 재귀가 빠른 것도 있지만, 대개 반복문이 함수 호출보다 더 빠르다.)

재귀함수 사용해보기

1. 팩토리얼(factorial)

function facto(n) {
  if (n === 0 || n === 1) return 1;
  return n * facto(n - 1);
}

console.log(facto(5)); // 120

팩토리얼은 0!과 1! 일 때 1이므로 함수의 종료 조건으로 사용하였다.
facto 함수 내부에서 리턴 값으로 자기 자신을 호출하고 있다.
현재 팩토리얼 재귀함수는 n에서 1씩 감소한 값을 넣어 호출하고 있으므로 n이 1이상인 경우 1이 되었을 때 더이상 재귀호출을 하지 않는다. (하한선 존재)
만약, 감소가 아닌 n에서 1씩 증가하는 함수였다면 언제 재귀를 멈출지 상한선을 만들어주면 된다.

2. 피보나치 수열

처음 두개의 항은 1이고 그 다음 항은 바로 앞 두 항의 합인 수열을 피보나치 수라 한다.

function fibo(n) {
  if (n <= 1) return n;
  return fibo(n - 1) + fibo(n - 2);
}

console.log(fibo(5)); // 5

두개의 항의 합인 수를 만들기 위해서 1이 1보다 큰 수일 때 n - 1, n - 2 한 값을 더하는 재귀 함수를 만들어주었다.
만약, n이 2라면 재귀호출 될 때 값이 1 + 0 이 되므로 1이 출력될 것이다.

---

참고 자료
큰돌의 터전
모던 자바스크립트 튜토리얼 재귀와 스택