[알고리즘] 헬퍼 메소드 재귀 vs 순수 재귀

재귀는 강력한 도구지만, 구현 방식에 따라 복잡도와 유지 보수성이 크게 달라질 수 있다.
특히 헬퍼 메소드 재귀(helper method recursion) 와 순수 재귀(pure recursion) 는 매우 자주 비교되는 두 가지 재귀 구현 방식이다.

 

헬퍼 메소드 재귀 (Helper Method Recursion)

외부 함수 안에 정의된 내부 헬퍼 함수가 재귀적으로 호출되는 구조

• 외부 함수는 한 번만 호출됨
• 내부의 헬퍼 함수가 재귀 호출을 담당
• 주로 결과값을 누적할 변수(result)를 외부에 선언해서 공유
• 로직이 분리되어 구조가 명확하고 직관적

function outer() {
  let result = [];

  function helper(input) {
    // 재귀 호출
  }

  helper(someInput);
  return result;
}

 

 

순수 재귀 (Pure Recursion)

함수 스스로가 자기 자신을 재귀적으로 호출하며 결과를 리턴값으로 누적하는 방식

• 외부 상태나 변수를 사용하지 않음
• 함수 내에서 모든 계산과 상태 전달이 일어남
• 불변성(immutability) 을 유지하며, 보통 slice, concat 등으로 새로운 값을 리턴

function pureRecursive(input) {
  if (input.length === 0) return [];

  return [..., pureRecursive(...)];
}

📌 두 방식은 서로 대체 가능한 관계이다.
구현 목적과 코드 스타일에 따라 적절히 선택할 수 있다. 

 

---

예제: 배열에서 홀수만 추출하기 (collectOddValues)

헬퍼 메소드 재귀 방식

function collectOddValues(arr) {
  let result = [];

  function helper(helperInput) {
    if (helperInput.length === 0) return;

    if (helperInput[0] % 2 !== 0) {
      result.push(helperInput[0]);
    }

    helper(helperInput.slice(1));
  }

  helper(arr);
  return result;
}

• 외부 함수 collectOddValues는 한 번만 호출됨
• 내부 함수 helper는 재귀적으로 자기 자신을 호출
• 결과(result)는 외부 스코프에 존재 → 재귀 호출마다 값을 유지함
• 비교적 초보자에게 직관적이며 상태 추적이 용이

 

순수 재귀 방식

function collectOddValues(arr) {
  if (arr.length === 0) return [];

  let first = arr[0] % 2 !== 0 ? [arr[0]] : [];

  return first.concat(collectOddValues(arr.slice(1)));
}

 

• 함수 자체가 재귀적
• 외부 변수 없음 (상태 없음)
• concat을 이용해 리턴값으로만 결과 누적
• 매 호출마다 새로운 배열을 생성 → 메모리 사용량 증가 가능성
• 코드가 짧고 깔끔하지만 처음엔 직관적으로 이해하기 어려울 수 있음

---

주요 차이점 비교

1. 상태 유지 방식

• 헬퍼 메소드 재귀는 result 같은 외부 상태를 공유해서 여러 호출에서 결과를 유지한다. 
• 순수 재귀는 리턴값만 사용해 결과를 누적. 외부 변수나 상태를 사용하지 않는다.

2. 배열 복사와 불변성

• 순수 재귀에서는 slice, concat 등을 매 호출마다 사용하여 배열의 복사본을 생성한다.
• 이 방식은 불변성을 지키지만, 성능 측면에서 느릴 수 있다.

3. 가독성과 유지보수

• 헬퍼 메소드 방식은 초보자에게 명확한 흐름을 제공하지만, 여러 함수가 중첩되고 상태가 외부에 있어 추적이 어려울 수 있다.
• 순수 재귀는 간결하고 함수형 프로그래밍에 어울리지만, 스택 프레임과 리턴 흐름을 이해하기 어렵다. 

---

마무리 

• 헬퍼 메소드 재귀는 외부 상태를 통해 재귀 내에서 데이터를 축적
• 순수 재귀는 반환값만으로 재귀 결과를 조합
• 목적과 상황에 따라 두 방식 모두 유용하게 쓰일 수 있음