210903 재귀 알고리즘
3387 단어 JavaScript알고리즘JavaScript
문제
재귀를 사용하여 팩토리얼(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() 함수가 호출되서 어찌보면 반복되게 된다
Author And Source
이 문제에 관하여(210903 재귀 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@beanlove97/210903-재귀-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)