재귀함수의 이해 및 구현

재귀함수(Recursion Function)란

함수 안에 자신의 함수를 다시 호출하는 함수를 의미합니다.

이러한 재귀함수는 자신의 로직을 내부적으로 반복하다가, 일정한 조건이 만족되면 함수를 이탈하여 결과를 도출합니다.

---

재귀함수의 구현방법

 

예시1.

function countdown(n) {
	if(n > 0) {
    	console.log(n);
        return countdown(n-1);
    }
}

countdown(5);

결과값

5
4
3
2
1

 

예시2. 팩토리얼

function factorial(num) {
	if(num <= 1) {
    	return 1;
    }
    return num * factorial(num - 1);
}

const num = 5;
let result = factorial(num);
console.log(`${num}! = ${result}`);

결과값

5! = 120

회차	결과
1	5 * factorial(5-1)
2	5 * 4 * factorial(4-1)
3	5 * 4 * 3 * factorial(3-1)
4	5 * 4 * 3 * 2 * factorial(2-1)
5	5 * 4 * 3 * 2 * 1

팩토리얼은 양의 정수에 대해서 자신보다 작거나 같은 모든 양의 정수의 곱을 의미한다. (팩토리얼은 !로 표시한다)

예를 들어서 5!는 5*4*3*2*1의 결과인 120이 되는것이다.

 

위의 예시에서 factorial 함수는 파라미터 num을 1개 받고 있는데, 이때 들어온 num이 1보다 작거나 같은 값이면 바로 함수를 종료시킨다.

1보다 큰 값이라면 자신의 값과 자신보다 1 작은 값을 다시 factorial 함수의 파라미터로 넘겨준다.

 

예시3. 최대공약수 구하기

function fnGCD(num1, num2) {
	retrun (num1 % num2) ? fnGCD(num2, num1 % num2) : num2;
}

fnGCD(21, 14);

결과값

7