31. 자바스크립트 재귀 함수 (Recursive Functions)

재귀 함수 (Recursive Functions)

자바스크립트(JavaScript)에서 재귀 함수(Recursive Functions)는 함수(Function)가 스스로를 호출하여 문제를 해결하는 방식이다. 반복적인 작업을 간결하게 표현하며, 특히 트리(Tree)나 그래프(Graph) 같은 복잡한 데이터 구조를 다룰 때 유용하다. 재귀 함수(Recursive Functions)의 정의, 구현 방법, 일반 반복문과의 차이, 활용 사례를 살펴보자.

재귀 함수(Recursive Functions)는 자기 자신을 호출한다는 점에서 독특하다. 이를 통해 코드가 단순해지고, 문제 해결이 직관적으로 변한다. 자바스크립트(JavaScript)에서 재귀 함수(Recursive Functions)는 함수형 프로그래밍(Functional Programming)과도 연관되며, 성능 최적화와 결합하면 강력한 도구가 된다. 다양한 예제를 통해 재귀 함수(Recursive Functions)의 동작 방식과 실용성을 확인한다.

재귀 함수(Recursive Functions)란 무엇인가?

재귀 함수(Recursive Functions)는 함수(Function)가 내부에서 자신을 호출하여 작업을 수행한다. 기저 조건(Base Case)과 재귀 조건(Recursive Case)으로 구성되며, 기저 조건에서 호출이 종료된다. 재귀(Recursion)는 수학적 귀납법과 비슷한 논리를 따른다.

간단한 예제로 팩토리얼(Factorial)을 계산하는 함수를 보자:

function factorial(n) {
    if (n <= 1) return 1; // 기저 조건
    return n * factorial(n - 1); // 재귀 조건
}
console.log(factorial(5)); // 120 (5 * 4 * 3 * 2 * 1)

위 코드에서 factorial(5)는 다음과 같이 동작한다:

• factorial(5) = 5 * factorial(4)
• factorial(4) = 4 * factorial(3)
• factorial(3) = 3 * factorial(2)
• factorial(2) = 2 * factorial(1)
• factorial(1) = 1 (기저 조건 도달)

결과적으로 호출 스택(Call Stack)이 쌓였다가 풀리며 5 * 4 * 3 * 2 * 1 = 120을 계산한다. 재귀 함수(Recursive Functions)는 종료 조건이 없으면 무한 호출에 빠질 수 있다:

function infinite() {
    return infinite(); // 무한 재귀 (Stack Overflow)
}
// infinite(); // 오류 발생

자바스크립트(JavaScript)에서 재귀 함수(Recursive Functions)는 호출 스택(Call Stack)의 크기 제한에 주의해야 한다. 너무 깊은 재귀(Recursion)는 스택 오버플로우(Stack Overflow)를 유발한다.

화살표 함수(Arrow Functions)로도 구현 가능하다:

const factorialArrow = n => n <= 1 ? 1 : n * factorialArrow(n - 1);
console.log(factorialArrow(5)); // 120

재귀 함수(Recursive Functions)는 문제를 작은 하위 문제(Subproblem)로 나누어 해결하는 분할 정복(Divide and Conquer) 전략과 밀접하다.

재귀 함수(Recursive Functions)의 구현 방법

재귀 함수(Recursive Functions)는 기본 재귀와 꼬리 재귀(Tail Recursion)로 나뉜다.

1. 기본 재귀

기저 조건과 재귀 조건을 명시한다.

function sumToN(n) {
    if (n <= 1) return n;
    return n + sumToN(n - 1);
}
console.log(sumToN(5)); // 15 (5 + 4 + 3 + 2 + 1)

피보나치 수열(Fibonacci Sequence) 예제:

function fib(n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}
console.log(fib(6)); // 8

2. 꼬리 재귀(Tail Recursion)

마지막 연산이 재귀 호출인 경우로, 스택 프레임(Stack Frame)을 재사용할 수 있다. (자바스크립트 엔진은 최적화 미지원)

function factorialTail(n, acc = 1) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc);
}
console.log(factorialTail(5)); // 120

꼬리 재귀는 스택 오버플로우(Stack Overflow)를 줄일 잠재력이 있지만, 자바스크립트(JavaScript)에서는 기본적으로 최적화되지 않는다.

재귀 함수(Recursive Functions)와 반복문의 차이

재귀(Recursion)와 반복(Iteration)은 동일한 문제를 다른 방식으로 해결한다.

1. 코드 표현

- 반복문: 명시적 루프 사용.

function sumToNLoop(n) {
    let sum = 0;
    for (let i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}
console.log(sumToNLoop(5)); // 15

- 재귀: 함수 호출로 표현.

function sumToNRec(n) {
    if (n <= 1) return n;
    return n + sumToNRec(n - 1);
}
console.log(sumToNRec(5)); // 15

2. 성능

- 반복문: 스택 사용 없이 실행, 일반적으로 빠르다.

- 재귀: 호출 스택(Call Stack)을 쌓아 메모리 사용이 늘어난다.

console.time("Loop");
sumToNLoop(1000);
console.timeEnd("Loop");

console.time("Recursion");
sumToNRec(1000);
console.timeEnd("Recursion");
// Loop가 더 빠름

실무 예제

재귀 함수(Recursive Functions)의 실무 활용 사례를 통해 그 유용성을 확인한다.

1. 트리 순회(Tree Traversal)

const tree = {
    value: 1,
    children: [
        { value: 2, children: [{ value: 4 }] },
        { value: 3 }
    ]
};
function printTree(node) {
    if (!node) return;
    console.log(node.value);
    if (node.children) node.children.forEach(child => printTree(child));
}
printTree(tree); // 1, 2, 4, 3

2. 깊은 복사(Deep Copy)

function deepCopy(obj) {
    if (typeof obj !== "object" || obj === null) return obj;
    const result = Array.isArray(obj) ? [] : {};
    for (let key in obj) {
        result[key] = deepCopy(obj[key]);
    }
    return result;
}
const nested = { a: 1, b: { c: 2 } };
const copy = deepCopy(nested);
copy.b.c = 3;
console.log(nested.b.c); // 2

3. 배열 평탄화(Flatten Array)

function flatten(arr) {
    return arr.reduce((acc, item) => {
        return acc.concat(Array.isArray(item) ? flatten(item) : item);
    }, []);
}
const nestedArray = [1, [2, [3, 4], 5]];
console.log(flatten(nestedArray)); // [1, 2, 3, 4, 5]

4. 하노이 탑(Tower of Hanoi)

function hanoi(n, from, to, aux) {
    if (n === 1) {
        console.log(`원판 1을 ${from}에서 ${to}로 이동`);
        return;
    }
    hanoi(n - 1, from, aux, to);
    console.log(`원판 ${n}을 ${from}에서 ${to}로 이동`);
    hanoi(n - 1, aux, to, from);
}
hanoi(3, "A", "C", "B");
// 원판 1을 A에서 C로 이동
// 원판 2를 A에서 B로 이동
// 원판 1을 C에서 B로 이동
// 원판 3을 A에서 C로 이동
// ...

5. JSON 파싱

function parseJson(obj) {
    if (typeof obj !== "object" || obj === null) return obj;
    const result = {};
    for (let key in obj) {
        result[key] = parseJson(obj[key]);
    }
    return result;
}
const jsonData = { a: 1, b: { c: "2", d: { e: 3 } } };
console.log(parseJson(jsonData)); // 동일 구조 유지

6. 순열 생성(Permutations)

function permute(arr) {
    if (arr.length <= 1) return [arr];
    const result = [];
    for (let i = 0; i < arr.length; i++) {
        const current = arr[i];
        const rest = arr.slice(0, i).concat(arr.slice(i + 1));
        const perms = permute(rest);
        perms.forEach(p => result.push([current].concat(p)));
    }
    return result;
}
console.log(permute([1, 2, 3])); // [[1, 2, 3], [1, 3, 2], [2, 1, 3], ...]

7. 파일 시스템 탐색

const fsStructure = {
    name: "root",
    type: "folder",
    contents: [
        { name: "file1.txt", type: "file" },
        { name: "subfolder", type: "folder", contents: [{ name: "file2.txt", type: "file" }] }
    ]
};
function listFiles(dir) {
    if (dir.type === "file") return [dir.name];
    return dir.contents.reduce((acc, item) => acc.concat(listFiles(item)), []);
}
console.log(listFiles(fsStructure)); // ["file1.txt", "file2.txt"]

8. 숫자 분해 합

function digitSum(n) {
    if (n < 10) return n;
    return (n % 10) + digitSum(Math.floor(n / 10));
}
console.log(digitSum(1234)); // 10 (1 + 2 + 3 + 4)

성능과 한계

장점

- 간결함: 복잡한 로직을 단순화한다.

- 직관성: 분할 정복(Divide and Conquer) 문제에 적합하다.

- 유연성: 데이터 구조 처리에 강하다.

한계

- 스택 오버플로우(Stack Overflow): 깊은 재귀(Recursion)는 메모리 문제를 일으킨다.

- 성능: 반복문보다 느릴 수 있다.

메모이제이션(Memoization)이나 꼬리 재귀(Tail Recursion)로 성능을 개선할 수 있다.

마무리

재귀 함수(Recursive Functions)는 자바스크립트(JavaScript)에서 강력한 문제 해결 도구다. 사례를 통해 그 유용성을 확인했다.