210903 재귀 알고리즘

문제

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

1! = 1
2! = 1 * 2
5! = 1 * 2 * 3 * 4 * 5

새로 배우는 개념

재귀 (recursion)
자신을 정의할 때 자기 자신을 호출하는 방법
프로그래밍의 함수정의에서 많이 사용된다.

const countdown = n => {
  console.log(n);
  countdown(n-1);
}

countdown(10);

countdown 함수는 받은 인자를 console로 출력합니다.
그런데 위의 함수를 실행하면 10에서 시작해서 무한으로 마이너스 값까지 내려갑니다.

그래서 재귀함수는 아래의 절차가 꼭 필요합니다.
언제 멈출것인가?

위를 고려해 0이 되면 더이상 재귀를 이어나가지 않도록 종료 조건 을 추가하겠습니다.

const countdown = n => {
  console.log(n);

  if (n === 0) return;

  countdown(n-1);
}

countdown(10);

문제이해

팩토리얼의 원리 자체가

5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
0! = 1

이런식이기 때문에 결론적으로는

5! = 5 * 4 * 3 * 2 * 1 * 0!

이런식으로 계산을 해야한다

정답

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

코드설명

종료조건을 if(n===1) 으로 하게 되면 0!은 무한대로 돌아가기 때문에 에러가 발생한다

그렇기 때문에 n <= 1으로 조건을 설정해서
0!, 1!일 때에는 반환되는 값이 1이 되게 하고
그 밖에는 n * factorial(n - 1) 을 반환되게 하는데
이 때 factorial(n - 1)일 때에는 다시 factorial() 함수가 호출되서 어찌보면 반복되게 된다