[JS] 재귀 함수

재귀 함수

함수가 자기 자신을 호출하는 것을 재귀 호출이라 한다.
재귀 함수는 자기 자신을 호출하는 행위, 즉 재귀 호출을 수행하는 함수를 말한다.
재귀함수는 반복되는 처리를 위해 사용한다.

10부터 0까지 출력하는 함수를 구현.

function countdown(n){
	for(let i = n; i >= 0; i--) console.log(i);
}
countdown(10);

위의 함수는 문제없이 잘 동작하지만, 반복문 없이도 구현할 수 있는 방법이 바로 재귀함수를 사용하는 것이다.

function countdown(n){
	if(n<0) return;
    console.log(n);
    countdown(n-1);  // 재귀호출
}
countdown(10);

이처럼 자기 자신을 호출하는 재귀 함수를 사용하면 반복되는 처리를 반복문 없이 구현할 수 있다.

	// 팩토리얼 (계승)은 1부터 자신까지의 모든 양의 정수의 곱이다.
	// n! = 1*2*...*(n-1)*n
function factorial(n){
	// 탈출 조건 : n이 1 이하일 때 재귀 호출을 멈춘다.
  	if(n<=1) return 1;
    // 재귀 호출 
    return n * factiorial(n-1);
}
console.log(factorial(0)); // 0! = 1
console.log(factorial(1)); // 1! = 1
console.log(factorial(2)); // 2! = 2*1 = 2
console.log(factorial(3)); // 3! = 3*2*1 = 6
console.log(factorial(4)); // 4! = 4*3*2*1 = 24
console.log(factorial(5)); // 5! = 5*4*3*2*1 = 120

factorial 함수 내부에서 자기 자신을 호출 할 때 사용한 식별자 factorial은 함수 이름이다.
함수 이름은 함수 몸체 내부에서만 유효하다. 따라서 함수 내부에서는 함수 이름을 사용해 자기 자신을 호출 할 수 있다.
함수 외부에서 함수를 호출할 때는 반드시 함수를 가리키는 식별자로 해야 한다.

let factorial = function foo(n){
	// 탈출 조건 : n이 1 이하일 때 재귀 호출을 멈춘다.
  	if(n<=1) return 1;
    // 함수를 가리키는 식별자로 자기 자신을 재귀 호출 
    return n * factiorial(n-1);
    // 함수 이름으로 자기 자신을 재귀 호출 할 수도 있다.
    // console.log(factorial === foo);  // true
    // return n * foo (n-1);
};
console.log(factorial(5)); // 5! = 5*4*3*2*1 = 120

재귀 함수는 자신을 무한 재귀 호출한다. 따라서 재귀 함수 내에는 재귀 호출을 멈출 수 있는 탈출 조건을 반드시 만들어야 한다.
탈출 조건이 없으면 함수가 무한 호출되어 스택 오버플로 에러가 발생한다.
대부분의 재귀 함수는 for문이나 while문으로 구현 가능하다.

function factorial(n){
  	if(n<=1) return 1;
  	let res = n;
  	while(--n) res *= n;
    return res;
}
console.log(factorial(0)); // 0! = 1
console.log(factorial(1)); // 1! = 1
console.log(factorial(2)); // 2! = 2*1 = 2
console.log(factorial(3)); // 3! = 3*2*1 = 6
console.log(factorial(4)); // 4! = 4*3*2*1 = 24
console.log(factorial(5)); // 5! = 5*4*3*2*1 = 120

재귀 함수는 반복되는 처리를 반복문 없이 구현할 수 있다는 장점이 있지만 무한 반복에 빠질 위험이 있고, 에러를 발생시킬수 있으므로 주의해야 한다.