재귀함수란?

재귀함수,, 너란 참
양파같은 아이,,
까도까도 끝이 없는 러시아 인형같은 아이!!

재귀란?

어떤 문제를 해결할때, 동일한 구조의 더 작은 문제를 해결함으로써 주어진 문제를 해결하는 방법

즉, 재귀는 문제를 쪼개지지 않을때까지 쪼개는 것이다.

가장 간단한 예로 n!(factorial)을 살펴보면,
n! 은 1부터 n까지 1씩 증가한 값을 곱한 결과이다.

이를 반복문으로 표현하면,

function fac(num){
  let result = 1;
  for(let i = 1; i <= num; i ++){
  result = result * i
 }
  return result
}

이 문제를 재귀적으로 생각해보자.
즉 문제를 쪼갤 수 있을 만큼 쪼개보면

n ! = n * (n-1)!

여기서 또 쪼개면

n! = n * n-1 * (n-2)!

이렇게 반복적으로 문제를 쪼갤 수 있는데,
문제를 쪼개다가 더이상 쪼갤 수 없는 경우가 발생한다.
이를 Base Case, 즉 재귀의 종료 지점이라고 하며,
쪼갤 수 있는 경우를 Recursive Case라 한다.

위 수식을 코드로 다시 정리해보면,

fac(n) = n * fac(n-1)

이를 또 쪼개면

fac(n) = n * (n-1) * fac(n-2)

이와 같은 흐름으로 진행이 되는 것이다.

fac(n) = n * (n-1) * (n-2) * ..... * 2 * 1 

즉, 재귀의 종료지점은 1이 되며

fac(n) = n * fac(n-1) 

n-1이 0이 될때, 즉 n이 1이 되는 경우라고 생각할 수 있다.

따라서 재귀함수를 작성할 때는
보통 종료지점을 예외 케이스로 먼저 명시해준다.

n!을 구하는 재귀함수

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