재귀함수(Recursion Function)

재귀(Recursion)란 무엇인가?

함수를 스스로 호출하는 것으로 어떤 문제를 해결할 때 구조는 동일하지만 더 작은 경우를 해결함으로써 그 문제를 해결하는 방법이 재귀이다.

 

재귀는 어떤 경우에 사용하면 좋은가?

1) 주어진 문제가 구조는 비슷하고 더 작은 문제로 나뉘어 질 수 없는 경우

2) 중첩된 루프가 많은 경우

3) 중첩의 정도를 미리 알 수 없는 경우

 

재귀의 장점과 단점

장점: 프로그램의 가독성이 좋다. 

단점: 호출마다 call stack이 새로 생성되어 메모리를 많이 사용한다. 호출 stack이 너무 커져서 메모리를 엄청나게 소비할 수 있다. 

 

재귀함수를 만드려면 base case와 recursive case로 나누어야 한다. 

재귀함수는 자기 자신을 호출하기 때문에 호출 stack이 커져 메모리를 많이 소비하고 무한 루프에 빠질 수 있다. 재귀함수를 만들 때 언제 재귀를 멈출지 알려 주어야 한다. 그래서 모든 재귀 함수는 기본 단계(base case)와 재귀 단계(recursive case)로 나눈다. 재귀 단계는 함수가 자기 자신을 호출하는 부분이고 기본 단계는 함수가 자기 자신을 다시 호출하지 않는 부분으로 무한 루프에 빠지지 않는 부분이다. 

 

재귀함수의 대표적인 예로써는 factorial, fibonacci 수열, tree 구조 탐색이 있다. 

factorial인 경우를 생각해 보자. factorial은 자연수 1부터 n까지의 곱을 계산하는 함수이다. 

5!은 1*2*3*4*5이다. 이것을 (1*2*3*4)*5로 두 부분으로 나누어 생각한다면 4!*5 라고 할 수 있다. 1~5까지 factorial을 살펴보자.

factorial(1) = 1

factorial(2) = (1) * 2 = 2

factorial(3) = (1 * 2) * 3 = 2! * 3

factorial(4) = (1 * 2 * 3) * 4 = 3! * 4

factorial(5) = (1 * 2 * 3 * 4) * 5 = 4! * 5

여기에서 우리는 규칙성을 발견하게 된다.

factorial(number) =(number - 1)! *  number

 

5!을 쪼갤 때 더 이상 쪼갤 수 없는 부분이 바로 0이다. 0!은 1이 리턴된다. 이것을 base case로 해서 무한루프를 빠져나갈 조건을 만든다. 이것을 자바스크립트로 작성하면 다음과 같다. 

function factorial(n) {
	//Base Case
	//n이 0이면 재귀를 더 이상 진행하지 않는다
	if (n === 0) {
		return 1;
	}
   //Recursive Case
	return n * factorial(n - 1);
}