재귀랄, 재귀함수가 뭐야?

최근 코딩테스트 스터디를 진행하면서 재귀함수를 이용해야 하는 부분이 있었는데 작성도, 해석도 어려워서
재귀함수의 개념을 잘 모르고 있었다는 점을 깨달았습니다.
이 포스팅은 개념을 다시 정리하고 빨리 해석하는 스킬을 얻기 위해 작성합니다!

읽는 시간 : 5분

 

재귀함수는

함수 내부에서 자기 자신을 다시 호출하는 함수입니다.
주로 트리 구조를 탐색할 때와 같이, 반복적인 구조를 간결하게 처리해야 하는 상황에서 자주 사용되고, 대부분은 for나 while 등의 순회문으로 대체 가능합니다. 

재귀 함수는 아래처럼 사용합니다.

function 재귀함수(입력값) {
  if (종료 조건) {
    return (결과);
  }
  // 1) 작은 문제로 축소 -> 탈출조건에 가까워지는 요소
  const smallerInput = …;
  // 2) 자기 자신 호출
  const partial = 재귀함수(smallerInput);
  // 3) partial 결과를 가공해서 return
  return 가공(partial);
}

 

재귀함수를 사용하는 예시를 보겠습니다. 

 

예시 1. 팩토리얼

팩토리얼이란 어떤 자연수를 1까지 차례대로 곱하는 연산을 말합니다.
예를 들어, 5팩토리얼은 5 × 4 × 3 × 2 × 1 = 120입니다.

팩토리얼을 구하는 로직을 반복문으로는 이렇게 구현할 수 있습니다.

function 재귀없는팩토리얼(자연수){
    let answer = 1;
    for(let i = 자연수 ; i > 0 ; i-- ) {
    	answer *= i;
    }
    return answer;
}

사실 이정도는 간단하지만 그래도 재귀로 바꿔보겠습니다!

function 재귀팩토리얼(자연수){
    if(자연수 === 1){
    	return 1; // 탈출조건
    }
    return 자연수 * 재귀팩토리얼(자연수-1);
}

 

예시 2. 피보나치 수열

이번에는 재귀함수로 작성했을 때 비효율이 발생할 수 있는 경우를 살펴보겠습니다.
대표적인 예로 피보나치 수열이 있습니다.

피보나치 수열은 앞의 두 수를 더해 다음 수를 만들어가는 수열입니다.
예를 들어 [1, 2, 3, 5, 8, 13, ...]과 같은 형태이고, 수학적으로는 다음과 같이 정의됩니다:

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n ≥ 2)

 

피보나치 수열을 재귀함수로 구현하면 이렇게 됩니다. 

function 피보나치(n){
	  if(n === 0 || n === 1){
	      return n; 
	  }
	  return 피보나치(n - 1) + 피보나치(n - 2)
}

피보나치(5);

얼핏 코드상으로 보기엔 깔끔해보이지만 이 로직은 동일한 연산작업을 여러번 합니다. 아래 그림을 보면 

n번째 피보나치 수열을 구하기 위해 n-2는 2번, n-3은 3번... 숫자가 크면 클수록 비효율적인 중복 연산은 많아집니다. 

(n번째 피보나치수를 구하는 다른 방법이 궁금하다면)

 

예시 3. 가능한 모든 조합을 구할 때 ✨

반면, 가능한 모든 조합을 구해야 하는 문제에서는 재귀함수가 매우 유용하게 사용됩니다.
특히, 깊이가 정해져 있거나 조건에 따라 조합을 생성해야 할 때는 반복문으로는 표현이 번거롭고 복잡해지는 반면, 재귀는 자연스럽고 간결한 구조로 표현할 수 있습니다.

예를 들어, 중복되지 않은 x개의 카드가 주어졌다고 가정합니다.
이 카드들 중에서 5장을 선택하여 만들 수 있는 모든 조합을 배열로 구하고 싶다면, 재귀를 활용한 방식이 가장 직관적이고 구현도 간단합니다.

function 조합만들기(cards) {
  const n = cards.length;
  const result = [];
  const picked = [];            // 지금까지 뽑은 문자들
  const used = Array(n).fill(false); // 각 카드 사용 여부

  function 카드뽑기재귀함수() {
    // 탈출조건 : 5글자 다 뽑음
    if (picked.length === 5) {
      result.push(picked.join('')); // picked를 result에 담음
      return;
    }
    // 진행조건 : 아직 5글자를 다 뽑지 않음
    for (let i = 0; i < n; i++) {
      if (used[i]) continue; //이미 뽑은 카드인 경우 다음 순회로 넘김
      used[i] = true;// 사용처리
      
      picked.push(cards[i]);
      카드뽑기재귀함수(); // ⭐
      
      picked.pop(); 
      used[i] = false;
    }
  }

  카드뽑기재귀함수();
  return result;
}

// 사용 예:
const cards = ['A','B','C','D','E','F'];
const allWords = 조합만들기(cards);
console.log(allWords);  // ["ABCDE","ABCDF","ABCED",… 등 총 P(6,5)=720개]

 

해석 꿀팁

재귀함수는 직접 만드는 것보다도, 로직이 어떻게 흘러가는지 파악하는 과정이 더 어렵게 느껴졌습니다.
특히 함수가 자기 자신을 여러 번 호출하며 상태가 바뀌는 과정을 머릿속으로 따라가는 게 쉽지 않았습니다.

그런데 아래와 같은 방법을 활용하면 조금 더 수월하게 흐름을 이해할 수 있었습니다:

• 호출 스택을 종이에 그려보기
  재귀 호출이 일어날 때마다 어떤 인자가 넘어가고, 언제 return 되는지를 단계별로 적어보면 흐름이 눈에 보입니다.
• 작은 숫자부터 시도해보기
  예를 들어 피보나치(3)처럼 아주 작은 입력부터 돌려보면서 어떤 순서로 함수가 호출되는지 관찰하면, 재귀 구조가 더 명확하게 보입니다.
• 종료 조건과 호출인자를 제대로 파악
  • Base case(종료 조건): “언제 자기 자신 호출을 멈추는가?”
  • Recursive case(재귀 호출): “언제, 어떤 인자로 다시 호출하는가?”

 

생각보다 기본서에 재귀함수에 대한 내용이 많지 않았는데, 이해에 도움이 되었길 바라면서 이만 총총입니다!

 

참고서적 : 자바스크립트 Deep Dive