들어가며

'재귀'라는 개념은 처음 보면 다소 추상적이라고 생각했습니다.
책을 읽으면서도 똑같이 지문에 반복시키면 되지 왜 재귀를 써야하지? 라는 의문이 들거라고 했는데, 네... 제가 그랬습니다. ㅎㅎ
함수가 자기 자신을 호출한다고 하는데, 그게 어떤 상황에서 필요한지, 그리고 왜 굳이 반복문이 아닌 재귀를 써야 하는지 감이 잘 오지 않았거든요.
아마 저처럼 생각하시는 분들이 많으실 것 같은데요. 이 글 말미에는 조금이나마 개념에 대해 이해하시는 데에 도움이 되기를 바라며 작성해보았습니다.

 

그렇다면 재귀는 정확히 무엇일까요?
재귀(recursion)란 어떤 함수가 자기 자신을 직접 또는 간접적으로 호출하는 구조를 말합니다.  
즉, 같은 구조의 문제를 조금 더 작게 나누고, 그 결과를 바탕으로 전체 문제를 해결하는 방법이에요.

예를 들어 컴퓨터에서 .txt 파일을 찾기 위해 폴더를 탐색한다고 했을 때,
어떤 폴더를 열었더니 그 안에 또 폴더가 있고, 그 안에도 또 다른 폴더가 있고…  
몇 단계가 중첩돼 있는지 알 수 없기 때문에, 이러한 구조는 반복문만으로는 유연하게 대응하기 어렵습니다.

특히 스크립트로 구현할 때는 하위 폴더마다 반복문을 중첩해 작성해야 하기 때문에 코드가 길어지고, 유지보수도 어려워집니다. 예를 들어 아래는 .txt 파일을 찾기 위해 2단계까지 반복문으로 구현한 코드입니다.

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

/**
 * findTxtFilesLevel2
 * - 지정된 디렉터리에서 최대 2단계 깊이까지 .txt 파일을 탐색하여 경로 출력
 * - 재귀를 사용하지 않고 반복문만으로 처리
 */
function findTxtFilesLevel2(directory) {
  const items = fs.readdirSync(directory); // 1단계: 최상위 디렉터리의 항목들

  for (const filename of items) {
    const fullPath = path.join(directory, filename); // 전체 경로 구성
    const stat = fs.statSync(fullPath); // 파일/디렉터리 여부 확인

    if (stat.isFile() && filename.endsWith('.txt')) {
      console.log(fullPath); // .txt 파일이면 출력
    } else if (stat.isDirectory()) {
      const subItems = fs.readdirSync(fullPath); // 2단계: 하위 디렉터리의 항목들

      for (const subfile of subItems) {
        const subPath = path.join(fullPath, subfile);
        const subStat = fs.statSync(subPath);

        if (subStat.isFile() && subfile.endsWith('.txt')) {
          console.log(subPath); // 2단계의 .txt 파일 출력
        }
      }
    }
  }
}

이처럼 반복문으로만 구현하면 하위 폴더를 몇 단계까지 들어가야 할지 모를 경우, 그 깊이만큼 반복문을 계속 추가해야 하므로 비효율적이겠죠.

반면 재귀를 사용하면, 같은 구조를 재사용하면서도 훨씬 간결하고 확장 가능한 코드가 됩니다. 아래 예시 코드를 볼까요?

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

/**
 * findTxtFiles
 * - 지정된 디렉터리 하위 모든 디렉터리를 재귀적으로 탐색
 * - 모든 깊이에서 .txt 파일을 찾아 경로 출력
 */
function findTxtFiles(directory) {
  const items = fs.readdirSync(directory); // 현재 디렉터리의 항목들

  for (const filename of items) {
    const fullPath = path.join(directory, filename); // 전체 경로 구성
    const stat = fs.statSync(fullPath); // 파일/디렉터리 여부 확인

    if (stat.isFile() && filename.endsWith('.txt')) {
      console.log(fullPath); // .txt 파일이면 출력
    } else if (stat.isDirectory()) {
      findTxtFiles(fullPath); // 디렉터리일 경우 재귀 호출 → 하위 구조 계속 탐색
    }
  }
}

이 함수는 파일과 폴더를 구분해서 처리하는데, 폴더일 경우 동일한 로직을 재귀적으로 호출하여 안으로 들어가있는데요.
얼마나 깊이 들어갈지 몰라도 동작 방식은 늘 같기 때문에, 이처럼 반복적 구조를 가진 문제에서는 재귀가 코드적으로도 훨씬 깔끔하고 유연하게 처리할 수 있습니다.

위 예제를 통해 반복문과 재귀는 결과적으로 비슷한 작업을 수행할 수 있지만, 문제를 해결하는 관점에서 보면 다르다는 것을 조금은 느끼셨을까요?

아래 표를 보면 그 차이를 더 쉽게 이해할 수 있습니다.

항목	반복문(Loop)	재귀(Recursion)
작동방식	명시적인 반복(for, while)	함수가 자기 자신을 호출
직관성	한 눈에 흐름이 보임	호출 흐름을 따라가야 함
코드 구조	절차적, 평면적	계층적, 나선형
메모리 사용	스택 적음	호출 스택 많이 사용
적합한 문제	반복 횟수가 정해진 작업	구조적 문제 (트리, 분할 등)

 

반복문은 정해진 횟수의 작업을 효율적으로 처리하는 데 강하고,  
재귀는 문제 구조 자체가 반복적일 때 더 자연스럽게 표현할 수 있습니다.

 

재귀를 사용함에 있어 조금 더 자세히 설명을 드리겠습니다.
재귀가 잘 동작하기 위해선 반드시 기저 조건(base case) 이 있어야 하는데요.
기저 조건이란 더 이상 문제를 쪼갤 수 없을 때, 함수 호출을 멈추는 기준입니다.
이게 없다면 함수는 계속 자기 자신을 호출하며 멈추지 않게 됩니다. (멈추지 않는 무한 반복은 무섭습니다..)

function countDown(n) {
  if (n === 0) return;  // 기저 조건
  console.log(n);
  countDown(n - 1);     // 재귀 호출
}

여기서 n === 0은 더 이상 쪼갤 수 없는 최소 단위이며, 이걸 만나면 더 이상의 호출을 하지 않고 반환됩니다.
재귀를 사용하실 때, 기저 조건이 없으면 재귀는 절대로 멈추지 않는다라는 정의를 꼭 기억해주세요.

 

재귀는 위에서 아래로 문제를 분해하는 식으로 진행되는데, 
이런 구조를 하향식 재귀(Top-down recursion)라고 부른다고 합니다.
대표적인 예로 팩토리얼 계산이 있는데요. (먼 옛날 수학의 정석에서 본 것 같은..팩토리얼...)
팩토리얼은 계승을 나타내는 수학 용어인데, 예를 들어 5!은 5 * 4 * 3 * 2 * 1과 같이 계산합니다.

function factorial(n) {
  if (n === 1) return 1;  // 기저 조건
  return n * factorial(n - 1);  // 하향식 재귀 호출
}

이 함수는 n이 1이 될 때까지 계속 곱하고, n이 1이 되면 계산을 멈추고 결과를 되돌리는 방식입니다. 큰 문제를 점점 단순한 문제로 바꿔가는 구조로, 재귀의 기본 형태를 보여주는 예라고 할 수 있죠.

 

하지만 재귀가 항상 효율적인 것만은 아닙니다. 
같은 계산을 반복해서 호출하게 되면 오히려 성능이 떨어질 수 있거든요. 
대표적인 예로 피보나치 수열이 있습니다. (1, 1, 2, 3, 5, 8, ... 이렇게 진행되는 수열 기억나시나요?)

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

위 함수는 간결하지만, 같은 값을 여러 번 계산하게 됩니다. 예를 들어 fib(5)를 호출하면 fib(3)이나 fib(2) 같은 호출이 중복되죠. 이러한 중복 호출이 쌓이면 성능이 급격히 떨어지게 됩니다.

이런 문제를 해결하는 대표적인 기법이 메모이제이션(Memoization) 입니다. 이미 계산한 결과를 저장해두고, 동일한 값이 들어오면 다시 계산하지 않고 저장된 값을 사용하는 방식입니다.

const memo = {};

function fib(n) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n]; // 저장된 값 재사용
  return memo[n] = fib(n - 1) + fib(n - 2);
}

이렇게 하면 fib(3), fib(2) 같은 값은 한 번만 계산되고, 그 이후에는 저장된 결과를 빠르게 사용할 수 있어 훨씬 효율적입니다.

 

재귀가 특히 잘 작동하는 구조는 문제를 쪼개고 나누는 구조, 즉 분할 정복(Divide and Conquer) 알고리즘이라고 합니다.
이 방식은 문제를 작은 단위로 나누고, 각 단위를 해결한 다음, 결과를 모아서 최종 문제를 푸는 구조인데요. 
퀵 정렬(Quick Sort)은 그 대표적인 예입니다.

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = arr.slice(1).filter(x => x <= pivot);
  const right = arr.slice(1).filter(x => x > pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}

배열을 기준값(pivot)을 중심으로 작거나 같은 값, 큰 값으로 나눈 뒤, 각각 다시 정렬하고 합칩니다. 이 구조 자체가 문제를 나누고 해결하고 합치는 흐름이기 때문에 재귀가 특히 자주 사용되는 대표적인 구조입니다.

비슷한 방식으로 정렬이 아닌 값을 찾을 때 사용하는 퀵 셀렉트(Quick Select) 알고리즘도 있습니다. 
정렬 없이도 k번째 작은 값을 빠르게 찾는 알고리즘으로, 필요 없는 쪽은 더 이상 재귀 호출하지 않기 때문에 더 빠릅니다.

function quickSelect(arr, k) {
  if (arr.length === 1) return arr[0];
  const pivot = arr[0];
  const left = arr.slice(1).filter(x => x < pivot);
  const right = arr.slice(1).filter(x => x >= pivot);

  if (k <= left.length) {
    return quickSelect(left, k);
  } else if (k === left.length + 1) {
    return pivot;
  } else {
    return quickSelect(right, k - left.length - 1);
  }
}

이 코드는 배열에서 기준값을 기준으로 작은 값, 큰 값으로 분할한 뒤, k가 어느 쪽에 위치하는지에 따라 필요한 방향으로만 재귀 호출을 진행합니다. 정렬을 하지 않고도 원하는 위치의 값을 빠르게 찾을 수 있어 효율적입니다.

 

참고 문서

누구나 자료 구조와 알고리즘 - 제이 웬그로우 저/심지현 역

 

마치며

재귀는 단순히 코드를 줄이기 위한 테크닉이 아니라, 복잡한 구조나 반복적인 문제를 해결하기 위한 생각의 틀이라고 할 수 있을 것 같습니다.
이번 글을 통해 재귀의 개념이 조금 더 가깝게 느껴지셨기를 바랍니다.

글은 여기까지이며, 혹시 수정할 내용이 있다면 언제든 알려주세요.
읽어주셔서 감사합니다. 🙇🏻‍♀️  
그럼 안녕히…👋 -The End-