재귀의 신

function solution(arr) {
    // 재귀 호출을 위한 내부 함수를 만든다.
    // 이 함수는 처리해야 할 배열의 부분을 인자로 받는다.
    function recursiveOR(currentArr) {
        // **베이스 케이스:** 만약 현재 처리할 배열이 비어있다면 (길이가 0이라면)
        if (currentArr.length === 0) {
            // 더 이상 OR 할 게 없으니 0을 반환하고 재귀를 멈춘다.
            return 0;
        }

        // **재귀 스텝:**
        // 1. 배열의 첫 번째 요소를 가져온다.
        const firstBinaryString = currentArr[0];
        // 2. 첫 번째 2진수 문자열을 10진수 정수로 바꾼다.
        const firstDecimalValue = parseInt(firstBinaryString, 2);

        // 3. 배열에서 첫 번째 요소를 제외한 '나머지' 부분을 만든다.
        const restOfArray = currentArr.slice(1);

        // 4. 첫 번째 값에다가 '나머지' 배열을 재귀적으로 OR 연산한 결과를 비트 OR 한다.
        // 그리고 그 결과를 반환한다.
        return firstDecimalValue | recursiveOR(restOfArray);
    }

    // solution 함수는 최초 호출될 때 전체 배열을 가지고 내부 재귀 함수를 호출한다.
    return recursiveOR(arr);
}

 

이 코드를 바탕으로 재귀 함수의 동작 원리를 설명하는 바이다.

1. 재귀 함수 내 return의 역할

재귀 함수 내부에서 return은 크게 두 가지 중요한 역할을 한다.

• 베이스 케이스에서의 return:
  • 이 return은 재귀 호출의 연속을 멈추는 역할을 한다. 만약 이 부분이 없다면 함수는 자신을 무한히 호출하게 되어 프로그램 오류로 이어질 것이다.
  • 베이스 케이스는 문제가 더 이상 작게 나뉠 수 없는 가장 기본적인 상태를 의미한다. 이 상태에서는 재귀 호출 없이도 문제의 답이 '즉시' 결정된다.
  • 베이스 케이스에서의 return은 그 기본적인 문제의 답을 반환하며, 이 값은 재귀 호출 스택을 거슬러 올라가며 최종 결과를 구성하는 '기초값'이 된다.
  • 제시된 예시 코드에서 currentArr.length === 0일 때 return 0; 하는 부분이 바로 베이스 케이스의 return이다. 빈 배열의 비트 OR 연산 결과는 0이므로, 여기서 0을 반환함으로써 재귀가 종료되고 계산이 시작되는 것이다.
• 재귀 스텝에서의 return:
  • 이 return은 현재 단계에서 수행한 작업 결과와 자기 자신을 재귀적으로 호출하여 얻은 '더 작은 문제의 결과'를 조합하여 반환하는 역할을 한다.
  • 즉, "나에게 주어진 문제 중 내가 처리할 부분을 처리하고, 나머지 부분은 재귀 호출된 네가 해결해서 그 결과를 가져와라. 그 결과를 나의 결과와 합쳐서 내 위의 호출자에게 넘겨주겠다." 와 같은 의미다.
  • 예시 코드에서 return firstDecimalValue | recursiveOR(restOfArray); 이 부분이 재귀 스텝의 return이다. 여기서 recursiveOR(restOfArray)는 '자기 자신을 더 작은 문제로 호출하는 부분'이며, 이 return은 현재 단계의 firstDecimalValue와 재귀 호출의 최종 결과를 비트 OR 연산하여 상위 호출자에게 전달하는 것이다.

2. 재귀 함수가 자신을 호출하는 방식

재귀 함수는 자기 자신의 함수 본문 안에서 다시 자기 자신을 호출한다. 그러나 이때 중요한 규칙이 있다.

• 자기 자신을 호출할 때는 반드시 처리해야 할 문제의 범위를 '줄여서' 넘겨주어야 한다.
• 문제의 크기가 점진적으로 작아져서 결국에는 베이스 케이스에 도달하도록 설계되어야 한다. 만약 문제의 크기가 줄어들지 않거나 베이스 케이스에 도달하지 못한다면 무한 재귀 호출에 빠지게 된다.
• 예시 코드에서 recursiveOR(restOfArray) 부분이 자기 자신을 호출하는 곳이다. 원래 인자였던 currentArr에서 첫 번째 요소를 제외한 restOfArray를 넘겨줌으로써, 재귀 호출될 때마다 배열의 길이가 하나씩 줄어들어 결국 길이가 0인 베이스 케이스에 도달하게 되는 구조이다.

3. 겉에서의 return (최초 호출 부분)

재귀 함수 자체가 아닌, 그 재귀 함수를 맨 처음 호출하는 부분 (예시 코드에서 solution 함수 안의 return recursiveOR(arr);)에서의 return은 조금 다른 의미를 가진다.

• 이 return은 "이제부터 recursiveOR 함수에게 arr 전체 배열을 가지고 문제를 풀도록 시킬 것이며, recursiveOR 함수가 모든 재귀 호출 과정을 거쳐 최종 결과를 내놓으면, 나는 그 결과를 받아서 반환할 것이다" 라는 역할을 한다.
• 이는 재귀 함수 내부의 return들과 달리, 재귀 호출의 '시작'을 알리고 그 '최종' 결과값을 받아서 반환하는 게이트웨이 역할을 한다고 볼 수 있다.

재귀 함수 디자인의 일반적인 접근 방식

훌륭하게 문제를 해결하는 재귀 함수를 설계하기 위한 일반적인 접근 방식은 다음과 같다.

1. 문제 정의를 명확히 하기:
   • 이 함수는 어떤 입력을 받아서 어떤 출력을 반환해야 하는지 정의한다.
   • 문제가 완전히 해결된 상태는 어떤 상태인지 파악한다.
2. 베이스 케이스 찾기:
   • 문제가 더 이상 쪼개지지 않는 가장 단순한 경우, 즉 '자명한 답'이 존재하는 경우를 찾는다.
   • 이 베이스 케이스에서는 재귀 호출 없이 곧바로 답을 return 해야 한다. 이 return이 재귀의 끝을 알리는 신호다.
3. 재귀 스텝 설계하기:
   • 베이스 케이스가 아닌 경우, 즉 더 큰 문제 상황을 고려한다.
   • 현재의 '큰 문제'를 해결하기 위해 '나와 똑같은 함수'에게 '조금 더 작은 문제'를 해결해 달라고 요청하는 방식을 생각한다. (이것이 재귀적 사고다.)
   • '더 작은 문제'는 반드시 베이스 케이스 방향으로 진행되어야 한다.
   • '더 작은 문제의 결과'가 주어졌다고 가정했을 때, 현재 단계에서 필요한 추가적인 계산이나 작업을 정의한다.
   • 현재 단계의 계산 결과와 재귀 호출로 얻은 '더 작은 문제의 결과'를 적절히 조합하여 return 한다. 이 return이 현재 단계의 결과를 상위 호출자에게 전달한다.
4. 함수 구조 잡기:
   • 일반적으로 함수의 시작 부분에 베이스 케이스 조건을 체크하는 if 문을 배치하고, 베이스 케이스일 경우 바로 return 하도록 한다.
   • 베이스 케이스가 아닐 경우, 재귀 스텝 코드를 작성하여 필요한 계산을 수행하고 자기 자신을 재귀적으로 호출한 후, 그 결과를 현재 단계의 계산과 조합하여 return 하도록 한다.
5. 최초 호출 고려하기:
   • 실제로 재귀 함수를 사용할 때는, 전체 문제를 가지고 재귀 함수를 한 번만 호출하면 된다. 예시 코드의 solution(arr)에서 return recursiveOR(arr);처럼 말이다.