[nodeJS] Node.js에서 재귀 함수 이해하고 활용하기

재귀 함수는 프로그래밍에서 중요한 개념으로, 함수가 자기 자신을 호출하여 문제를 해결하는 방법입니다. 재귀를 잘 활용하면 복잡한 문제를 간단하게 해결할 수 있지만, 잘못 사용하면 무한 루프나 메모리 초과를 초래할 수 있습니다.

 

1. 재귀 함수란

재귀 함수(Recursive Function)

• 함수가 자기 자신을 호출하는 함수
• 재귀는 특정 문제를 더 작은 하위 문제로 나누어 반복적으로 해결하는 데 유용
• 재귀는 수학적 개념이나 알고리즘 문제를 해결할 때 자주 사용

기본 구조

1. 기본 종료 조건(Base Case): 재귀가 끝나는 조건. 이 조건이 없으면 함수는 계속해서 자기 자신을 호출하여 무한 루프에 빠질 수 있음.
2. 재귀 단계(Recursive Step): 문제를 더 작은 하위 문제로 나누어 자기 자신을 호출하는 부분.

 

2. 재귀 함수의 구조와 기본 예제

[구조 설명]

function recursiveFunction(parameter) {
  if (baseCondition) { // 기본 종료 조건
    return baseValue;
  }
  // 재귀 호출
  return recursiveFunction(smallerParameter);
}

 

[간단한 예제: 팩토리얼 계산]

• 팩토리얼은 n! = n × (n - 1) × ... × 1로 정의되며, 재귀로 쉽게 표현 가능
• factorial 함수는 기본 종료 조건 n <= 1이 될 때까지 계속해서 자기 자신을 호출.

function factorial(n) {
  if (n <= 1) return 1; // 기본 종료 조건
  return n * factorial(n - 1); // 재귀 호출
}

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

 

3. 재귀 함수의 장점과 단점

장점

1. 문제를 간단하게 표현: 재귀는 복잡한 문제를 간단하고 직관적으로 표현 가능
2. 자연스러운 구현: 트리나 그래프와 같은 자료 구조를 다룰 때 재귀는 자연스러운 구현 방법으로 표현 가능

단점

1. 성능 문제: 재귀 호출이 너무 깊어지면 스택 오버플로우(Stack Overflow)가 발생 가능
2. 메모리 사용: 재귀 함수는 호출 스택에 함수 호출을 계속해서 저장하므로 메모리 사용 증가

 

4. Node.js에서 재귀 함수 활용하기

• Node.js에서 재귀 함수는 파일 시스템을 탐색하거나 비동기 작업을 처리하는 데 유용
• 주어진 디렉토리의 모든 파일과 하위 디렉토리를 탐색하며, 재귀를 사용하여 디렉토리 구조를 깊이 탐색

const fs = require('fs');
const path = require('path');

function readDirectory(directory) {
  const files = fs.readdirSync(directory);

  files.forEach(file => {
    const fullPath = path.join(directory, file);
    if (fs.lstatSync(fullPath).isDirectory()) {
      // 디렉토리인 경우 재귀 호출
      readDirectory(fullPath);
    } else {
      console.log('파일:', fullPath);
    }
  });
}

readDirectory('./example-directory');

 

5. 재귀 함수 최적화 기법

1) 꼬리 재귀 최적화(Tail Recursion)

• 함수의 마지막 작업이 자기 자신을 호출하는 형태의 재귀
• 일부 컴파일러는 꼬리 재귀를 최적화하여 호출 스택을 줄여주지만 JavaScript는 꼬리 재귀 최적화를 지원하지 않기 때문에 반복문으로 사용

2) 메모이제이션(Memoization)

• 메모이제이션은 이전에 계산한 결과를 저장하여 동일한 작업을 반복하지 않도록 하는 기법
• 피보나치 수열을 메모이제이션을 사용하여 구현
• memo 객체를 사용하여 피보나치 수열의 중복 계산을 방지

function fibonacci(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

console.log(fibonacci(10)); // 출력: 55

 

3) 반복문으로 재구성

• 재귀를 반복문으로 변환하면 호출 스택 감소 가능

function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

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

 

 

 

재귀 함수는 문제를 분할하여 해결하는 강력한 도구입니다. Node.js에서 재귀 함수를 사용할 때는 기본 종료 조건을 잘 설정하고, 메모리 사용을 관리하며, 필요에 따라 최적화 기법을 적용하는 것이 중요합니다. 특히, 재귀와 반복의 장단점을 이해하고 상황에 맞는 방법을 선택하는 것이 핵심입니다.