[algorithm] 재귀와 재귀함수에 대한 이해

재귀는 어떤 것을 정의할 때, 자기 자신을 참조하는 것을 의미합니다. 프로그래밍에서는 주로 함수가 자기 자신을 호출하는 방식으로 구현됩니다. 이를 재귀함수라고 합니다. 재귀는 문제를 더 작은 하위 문제로 나누어 해결하는 데 유용합니다.

콜스택(Call Stack) 이해하기

콜스택은 함수 호출이 이루어질 때마다 함수의 정보를 저장하는 메모리 영역입니다. 함수가 호출되면 콜스택에 등록되고, 함수가 종료되면 콜스택에서 제거됩니다. 이 과정을 통해 함수 호출 순서와 현재 실행 중인 함수를 관리합니다.

예제: 콜스택 동작

function a() {
	console.log('a');
	b();
}

function b() {
	console.log('b');
	c();
}

function c() {
	console.log('c');
}

a();

 

이 예제를 실행하면 콜스택의 변화는 다음과 같습니다:

1. a 등록
2. b 등록
3. c 등록
4. c 제거
5. b 제거
6. a 제거

재귀함수를 호출할 때마다 콜스택에 함수가 추가되므로, 반복문으로 해결할 수 있는 문제를 재귀함수로 해결하면 비효율적일 수 있습니다.

재귀함수를 사용하기 좋은 패턴

재귀함수는 하위 문제의 결과를 기반으로 현재 문제를 계산하는 패턴에 적합합니다. 이러한 패턴의 예를 살펴보겠습니다.

하향식 계산 사례

1. 팩토리얼 계산

팩토리얼은 수학에서 주어진 양의 정수 𝑛n에 대해 1부터 𝑛n까지의 모든 정수를 곱한 결과를 의미합니다.

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

console.log(factorial(5)); // 출력: 120

2. 제곱 계산 (Power)

주어진 수 𝑥를 𝑛번 제곱하는 함수입니다.

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

console.log(power(3, 5)); // 출력: 243

3. 배열의 합 계산

배열의 모든 요소의 합을 계산하는 함수입니다.

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

console.log(sumArray([1, 2, 3, 4, 5])); // 출력: 15

결론

재귀는 문제를 더 작은 하위 문제로 나누어 해결할 수 있게 해주는 강력한 도구입니다. 하지만 재귀함수는 콜스택을 많이 차지할 수 있으므로, 상황에 따라 반복문으로 해결하는 것이 더 효율적일 수 있습니다. 재귀함수는 특히 하위 문제의 결과를 기반으로 현재 문제를 계산하는 패턴에서 유용하게 사용됩니다.