재귀 알고리즘 개념

• 어떤 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.
• 함수를 정의할 때 재귀적으로 정의된 함수를 재귀함수라고 부른다.

기저 조건 : Base Case

function myFunction(number) {
	console.log(number);
	myFunction(number + 1);
}

myFunction(1);

위의 함수를 실행시켜 보면 숫자가 빠르게 쌓이다 자동으로 함수가 종료된다. 이는 콜스택 메모리가 가득 찼기 때문에 종료되는 것이다.

그렇다면 콜스택이란?
함수가 호출되면서 올라가는 메모리 영역으로 스택이라고도 불린다.
콜스택은 스택의 특성처럼 먼저 들어온 데이터가 나중에 나가는 특성을 가지고 있다. (Last In, First Out : LIFO) 함수를 호출하면 이 함수는 콜스택에 올라가게 되고 함수가 종료되면 콜스택에서 제거된다.

재귀 함수에서 콜스택 메모리가 가득 차게 된 이유는 종료 조건이 없기 때문에 발생하는 문제로, 재귀 함수에서는 탈출 조건, 즉 기저 조건(base case)이 반드시 있어야 한다.

기저 조건은 재귀 함수가 더 이상 자기 자신을 호출하지 않게 만드는 조건을 의미한다. 기저 조건은 재귀 함수가 무한 루프에 빠지지 않도록 하는 중요한 역할을 한다.

// 기저조건 추가
function myFunction(number) {
	if (number > 2) return;
	console.log(number);
	myFunction(number + 1);
}

위의 그림은 myFunction(1)을 실행했을 때의 콜스택 상황을 시각화 한 그림이다. 이 그림을 이해하고 넘어간다면 스택의 큰 그림을 이해했다고 생각한다.

재귀 함수 예제

팩토리얼

팩토리얼은 n이 주어졌을 때 1부터 n까지의 모든 수의 곱을 말한다.
재귀 함수를 작성하기 위해서는 재귀 함수 내에서 자기 자신을 호출할 때 이미 구현이 되어있다고 가정하는 편이 좋다. 예로 밑의 함수에서 number로 5가 들어온 상황에서 5!을 구현하는 방법은 5*4!을 구현하는 것과 같다.

function factorial(number) {
  if (number == 1 || number == 0) {
    return 1;
  } else {
    return number * factorial(number - 1);
  }
}

console.log(factorial(5));

재귀 함수의 패턴

단순한 반복 실행

for(let i = 1; i < 11; i++) {
	console.log(i);
}

function myFunction(number) {
	if(number > 10) return;
	console.log(number);
	myFunction(number + 1);
}
myFunction(1);

위의 코드는 같은 역할을 for문과 재귀 함수로 나누어 구현한 것이다.
단순한 반복 실행을 재귀로 구현하는 것은 반복문으로 구현했을 때 보다 이점이 없다. 오히려 콜스택의 공간을 많이 차지해 반복문보다 성능이 떨어진다는 단점이 있다.

하위 문제의 결과를 기반으로 현재 문제를 계산하는 패턴

return number * factorial(number - 1);

function factorial(number) {
	let sum = 1;
	for(let i = 1; i <= number; i++) {
		sum *= 1;
	}
	return sum;
}

위의 factorial은 재귀 함수를 사용하지 않고 for문을 이용해 구현할 수도 있다.
for문을 이용해서 계산하는 방식을 상향식 계산이라고 하며, 재귀를 이용해서 하위 문제의 결과를 기반으로 현재 문제를 계산하는 방식을 하향식 계산이라고 한다.

하향식 계산 방식은 오직 재귀함수로만 구현할 수 있으며, 재귀를 이용해서 모두 하향식 계산이라고 부르지는 않는다. 재귀를 이용해서 상향식 계산을 구현할 수도 있지만, 이 경우에는 for문보다 성능이 좋지 않아 사용할 이유가 마땅하지 않다.

// 재귀함수로 상향식 계산 방식을 구현한 예제
function factorial2(number, i = 1, sum = 1) {
	if( i > number) return sum;
	return factorial2(number, i + 1, sum * i);
}

하향식 계산 (Top-down computation)은 문제를 큰 단위에서 시작하여 더 작은 문제로 분해해 나가는 방식으로 동작한다.

상향식 계산 (Bottom-up computation)은 주로 반복문을 사용하여 작은 문제부터 시작하여 점점 큰 문제의 해답을 구하는 방식이다.

예제

function power(x, n) {
  if(n == 0) return 1;
  return power(x, n-1) * x;
}

function strLength(arr){
    if(arr[0] == null) return 0;
    return strLength(arr.slice(0, -1)) + 1;
}