Js _ 재귀함수

⏳ 문제
재귀를 사용하여 팩토리얼(factorial)을 구하는 함수를 구현해주세요. 팩토리얼이란 1에서부터 n까지의 정수를 모두 곱한것을 말합니다.

재귀함수란?

• 내부에서 자기 자신을 호출하는 함수
• 무한루프를 방지하기 위해 함수를 종료하는 조건식을 포함해야함
• 반복문보다 속도는 느리지만, 코드가 훨씬 짧음

재귀 함수 형태

const decreaseNum = n => {
  console.log(n);
  
  n = n - 1;
  if(n === 0) return 1;
  decreaseNum(n)
}

decreaseNum(5);  // 출력값: 5, 4, 3, 2, 1

풀이

const factorial = n => {
  if(n === 0) return 1;
  return n * factorial(n-1);
}

factorial(5)를 호출한다고 가정해보자.
5 x 4 x 3 x 2 x 1 순서대로 곱한 결과값을 구해야 한다.
그러기 위해서는 인자로 들어온 n의 값이 함수를 돌때마다 1씩 마이너스가 되어야 한다.

대신, 함수가 재귀를 멈추기 위해서는 n의 값이 1씩 마이너스 되다가 0이 되는 타임이다. n === 0일 때 멈추지 않으면, 음수값까지 계속 곱해지게 될 것이다.

if(n === 0) return 1 처럼 재귀를 멈추는 조건문에서 return 1을 한 이유는
factorial 함수가 n * factorial(n-1)값을 return 하는데,
5 x 4 x 3 x 2 x 1 의 값을 가지고 있는 상태에서 1을 곱하면 구하고자 하는 값인 120을 구할 수 있기 때문이다. 만약 return 0을 해버린다면, 120 * 0 = 0이 되어 원하는 값을 구할 수 없다.

자기 자신을 내부에서 부르는 형태이다보니, 어느 지점에서 어떤 값을 return 해주어야 하는지 고민을 꽤 했던 것 같다.