재귀 함수 왜 써요? 함수의 return과 매개변수, 스코프 200% 활용하기

 

자바스크립트 Deep Dive의 12장 함수 파트를 읽어보면, 자바스크립트에 관한 내용도 물론 있지만

함수라는 프로그래밍 언어 본질적인 녀석에 대한 설명을 많이 마주하게 됩니다.

 

여기에 나오는 재귀 함수라는 개념을 살펴보고, 이것이 왜 좋은지! 그리고 어떨때 써야 하는지를 간단하게 정리해 보겠습니다.

 

자기 자신을 반복하는 함수

지금은 종료되어버린 알고리즘 사이트 백준에는 재귀함수가 뭔가요? 라는 문제가 있었습니다.

 

 

위의 출력 예제처럼, 뭔가 반복되는 구조로 답을 출력해야 하는 문제였습니다.

 

우리가 프로그래밍을 배울때, 반복되는 것들을 다루기 위한 방법으로 가장 처음 배우는 것은 반복문입니다.

반복문은 쉽고 단순하고 강력하죠.

그래서 사실 위의 문제는 반복문으로도 풀 수 있어요.

 

function solution(n) {
  console.log('어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.');

  for (let i = 0; i < n; i++) {
    const prefix = '____'.repeat(i);
    console.log(prefix + `"재귀함수가 뭔가요?"`);
    console.log(prefix + `"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.`);
    console.log(prefix + `마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.`);
    console.log(prefix + `그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."`);
  }
  
  const prefix = '____'.repeat(n);
  console.log(prefix + `"재귀함수가 뭔가요?"`);
  console.log(prefix + `"재귀함수는 자기 자신을 호출하는 함수라네"`);
  console.log(prefix + `라고 답변하였지.`);

  for (let i = n - 1; i >= 0; i--) {
    const prefix = '____'.repeat(i);
    console.log(prefix + '라고 답변하였지.');
  }
}

solution(4);

 

하지만 뭔가 비효율적인 기분입니다.

분명 더 단순하게 풀어낼 수 있을 것만 같습니다.

위의 코드를 재귀함수를 이용하여 풀어내면 아래와 같아집니다.

 

function solution(n) {
  console.log('어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.');

  function recursion(depth) {
    const prefix = '____'.repeat(depth);

    console.log(prefix + `"재귀함수가 뭔가요?"`);

    if (depth === n) {
      console.log(prefix + `"재귀함수는 자기 자신을 호출하는 함수라네"`);
      console.log(prefix + `라고 답변하였지.`);
      return;
    }

    console.log(prefix + `"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.`);
    console.log(prefix + `마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.`);
    console.log(prefix + `그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."`);

    recursion(depth + 1);

    console.log(prefix + `라고 답변하였지.`);
  }

  recursion(0);
}

solution(4);

 

처음에 `recursion(0)` 으로 함수를 호출해서, 깊이가 n이 될때까지 그 내부에 있는 `recursion(depth + 1);` 을 호출하는 코드입니다.

안타깝게도 더 복잡해진 것 같네요!

네, 그렇습니다. 이 문제는 사실 반복문으로 푸는 것이 재귀를 이용하는 방법보다 읽기 쉽고 구현도 간단합니다.

재귀를 아무데나 쓰면 안 된다는 교훈(?)같은 문제였습니다.

 

재귀함수가 읽기 어려운 이유

위의 예제에서 본 것처럼 재귀함수는 종종 코드 줄 수가 비슷하거나 더 짧은데도 불구하고 읽기는 더 어렵게 느껴집니다. 왜 그럴까요?

가장 큰 이유는 우리가 코드를 읽는 방식과 재귀가 실행되는 방식이 다르기 때문입니다.

 

우리는 코드를 위에서 아래로 순서대로 읽습니다. 반복문도 그 흐름을 그대로 따라가요.

`for (let i = 0; i < n; i++)` 라는 반복문 코드는 i가 0에서 n-1까지 반복되며 위에서 아래로 순서대로 한 번씩 실행됩니다.

머릿속에 잘 그려지죠!

 

하지만 재귀는 다릅니다. 위의 예제에서 이 부분을 다시 살펴봅시다.

 

function recursion(depth) {
  const prefix = '____'.repeat(depth);
  console.log(prefix + `"재귀함수가 뭔가요?"`);
  if (depth === n) {
    // ...종료 조건
    return;
  }
  // ...중간 출력들
  recursion(depth + 1);                  // ← 자기 자신 호출
  console.log(prefix + `라고 답변하였지.`); // ← ??? 얘는 언제 실행되는 거지?
}

 

마지막 `console.log(prefix + '라고 답변하였지.');`는 도대체 언제 실행될까요?
`recursion(depth + 1)`이 호출되고, 그 안에서 또 호출되고, 또 호출되고... `depth === n`이 되어 종료 조건을 만나야 비로소 거꾸로 돌아오면서 실행됩니다.

 

recursion(0) 호출
  ├─ "재귀함수가 뭔가요?" 출력
  ├─ recursion(1) 호출
  │   ├─ "재귀함수가 뭔가요?" 출력
  │   ├─ recursion(2) 호출
  │   │   ├─ ... (계속 깊어짐)
  │   │   └─ 종료 조건 도달
  │   └─ "라고 답변하였지." 출력  ← 여기서 실행!
  └─ "라고 답변하였지." 출력      ← 그 다음 여기서 실행!

 

그니까 재귀함수는 깊이 파고 들어갔다가 다시 거슬러 올라오는 흐름을 가집니다.

요게 머릿속에 안 그려지면 코드 흐름을 따라가면서 읽기가 정말 어려워요.

그래서 개발을 처음 접하면 많이 헤매고는 합니다 (저도 그랬구요..)

 

return, 매개변수, 스코프를 이용해서 재귀함수 200% 활용하기

위의 "재귀함수가 뭔가요?" 예제에서는 사실 재귀의 강점이 잘 드러나지 않았어요. 단순히 들여쓰기 깊이를 늘리고 줄이는 정도라서, 반복문으로도 충분히 깔끔하게 해결되는 문제였거든요.

재귀가 진짜로 빛을 발하는 순간은 다음 세 가지를 함께 활용할 때입니다.

1. 매개변수: 상태를 깊이 따라 내려보낸다

위의 예제에서 depth가 그런 역할을 했어요. 함수가 호출될 때마다 depth + 1을 넘겨주면서, "지금 몇 번째 깊이에 있는지"를 매번 자연스럽게 전달했죠.

만약 반복문으로 비슷한 동작을 하려면 별도의 변수를 외부에서 관리해야 하지만, 재귀에서는 그냥 인자로 넘기면 끝입니다. 상태를 호출 스택을 따라 함께 끌고 가는 거예요.

 

function traverse(node, depth) {
  console.log(' '.repeat(depth * 2) + node.name);
  for (const child of node.children) {
    traverse(child, depth + 1); // depth가 자연스럽게 따라 내려감
  }
}

 

2. return: 결과를 거꾸로 쌓아 올린다

재귀의 진짜 힘은 return에서 나옵니다. 깊이 내려갔다가 거꾸로 돌아오면서, 각 단계의 결과를 모아 위로 올려보낼 수 있어요.

가장 고전적인 예시는 팩토리얼입니다.

 

function factorial(n) {
  if (n <= 1) return 1;          // 종료 조건
  return n * factorial(n - 1);   // 자기 자신을 호출한 결과를 활용
}
factorial(5); // 120

 

factorial(5)는 factorial(4)의 결과가 필요하고, 그건 또 factorial(3)의 결과가 필요하고... 이렇게 깊이 내려갔다가 factorial(1)이 1을 반환하는 순간부터 위로 올라오면서 결과가 누적됩니다. 5 * 4 * 3 * 2 * 1이라는 곱셈이 거꾸로 쌓이는 거죠.

이걸 반복문으로도 짤 수 있지만, 문제 자체가 "자기 자신으로 정의되는" 구조라면 재귀가 압도적으로 깔끔하게 표현됩니다.

3. 스코프: 각 호출은 자기만의 세계를 가진다

함수가 호출될 때마다 새로운 실행 컨텍스트가 생성됩니다. 즉, 각 호출마다 독립된 지역 스코프를 갖죠.

 

function recursion(depth) {
  const prefix = '____'.repeat(depth); // 호출마다 새로 만들어지는 지역 변수
  // ...
}

 

recursion(0)의 prefix와 recursion(1)의 prefix는 완전히 다른 변수예요. 서로 간섭하지 않습니다. 너무 당연한 얘기처럼 들리지만, 재귀에서는 이 특성이 정말 중요해요.

만약 스코프가 없어서 변수가 공유됐다면, 깊이 들어갔다가 돌아올 때 값이 덮어써져서 엉망이 됐을 겁니다. 호출 스택과 지역 스코프가 함께 작동하기 때문에, 우리는 "지금 이 호출에서의 값"을 다른 호출과 헷갈리지 않고 안전하게 다룰 수 있어요.

세 가지가 합쳐지면: 깊이를 알 수 없는 구조 다루기

매개변수, return, 스코프 이 세 가지가 합쳐지면, 반복문으로는 처리하기 까다로운 문제도 우아하게 풀어낼 수 있습니다.

대표적인 예가 중첩된 자료구조예요. 얼마나 깊이 중첩되어 있을지 미리 알 수 없는 경우죠.

 

// 깊이가 정해지지 않은 중첩 배열의 모든 숫자 더하기
function sumNested(arr) {
  let sum = 0;
  for (const item of arr) {
    if (Array.isArray(item)) {
      sum += sumNested(item); // 재귀 호출 → return으로 결과 합치기
    } else {
      sum += item;
    }
  }
  return sum;
}

sumNested([1, [2, [3, [4, [5]]]], 6]); // 21

 

이걸 반복문으로 짜려면 별도의 스택을 직접 만들어서 관리해야 합니다. 하지만 재귀로는 호출 스택이 알아서 그 역할을 해주죠. 매개변수로 현재 배열을 넘기고, 스코프 덕분에 각 호출의 sum이 섞이지 않고, return으로 안쪽 결과를 바깥쪽으로 올려보냅니다. 세 가지가 동시에 일하고 있는 거예요.

이런 패턴이 잘 어울리는 사례들이 있습니다.

• DOM 트리 순회
• 파일 시스템 탐색
• JSON 객체 깊은 복사 (deep clone)
• 트리/그래프 자료구조 다루기
• 백트래킹 알고리즘

공통점은 자료구조 자체가 재귀적이라는 거예요. 자기 자신과 똑같은 구조를 안에 또 품고 있는 형태죠. 이런 문제에는 자료구조의 모양과 코드의 모양이 자연스럽게 일치합니다.

 

 

정리: 언제 재귀를 써야 할까?

처음에 봤던 "재귀함수가 뭔가요?" 문제처럼 단순한 반복이라면 반복문이 훨씬 낫습니다. 읽기 쉽고, 함수 호출 비용도 없고, 디버깅도 편하니까요.

재귀를 꺼내드는 게 자연스러운 때는 이런 경우입니다.

• 문제 자체가 자기 자신으로 정의될 때 (팩토리얼, 피보나치)
• 데이터 구조가 재귀적일 때 (트리, 중첩 객체)
• 깊이를 미리 알 수 없을 때

이때 매개변수로 상태를 내려보내고, return으로 결과를 합쳐 올리고, 스코프로 각 호출의 독립성을 보장하면, 반복문으로는 흉내내기 힘든 우아한 코드가 나옵니다.

재귀를 두려워하지 말고, 그렇다고 남용하지도 말고, 문제의 모양에 맞춰 적재적소에 활용해 봅시다.