JS 재귀함수

Recursive Function
함수가 계속해서 자기 자신을 호출함(재참조)을 뜻한다.

함수를 실행할 때마다 스택에 쌓이게 되는데
끝없이 자기 자신을 실행하게 되면 스택의 공간이 한정적이라 스택 오버플로우 문제가 발생한다.
(스택=컴퓨터 메모리라서 메모리 공간의 한계가 있다)

재귀함수의 대표 예제

1. 팩토리얼

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

2. 피보나치 수
   (기본 코드)

function solution(n) { 
	let answer = 0;
 	if (n === 0) return 0;
 	else if (n === 1) return 1;
 	else return solution(n - 1) + solution(n - 2);
}

(참고 : 프로그래머스 피보나치 수 문제 풀이)

프로그래머스 피보나치 수 문제에 대해서는 기존 재귀함수 로직에 나머지 연산자가 필요하다.
하지만 이렇게 풀게되면 재귀호출의 시간복잡도-O(2^n)가 반복문-O(n)보다 크기 때문에 메모리를 많이 차지하여 시간초과가 뜬다.

// 시간초과
function solution(n) { 
	let answer = 0;
 	if (n === 0) return 0;
 	else if (n === 1) return 1;
 	else return (solution(n - 1) % 1234567) + (solution(n - 2) % 1234567);
}

따라서 이 문제의 경우 반복문으로 풀어야 한다. 이처럼 재귀함수가 코드 작성할 때는 간결해서 좋은데 시간복잡도가 크고 스택오버플로우 위험성이 있어서 항상 재귀로만 풀면 안된다.