자바스크립트 알고리즘 재귀(recursion) 개념과 예제

 

안녕하세요.

오늘은 자바스크립트 알고리즘 중 초반에 감 잡기 가장 힘든 개념 중 하나인 재귀에 대해 포스팅 해보려고 합니다. 

 

 

 

 

재귀란 무엇일까?

재귀는 어떤 함수가 자기 자신을 호출하는 기법입니다. 모든 재귀 함수는 종료 조건을 갖는데, 재귀 호출이 무한히 반복되지 않도록 하기 위해서지요. 재귀는 정말 여러 방면에서 사용하는데, DOM, JSON.parse 등과 같은 기본적인 자바스크립트 실행 코드들에도 재귀가 들어있습니다. 재귀를 사용하면 복잡한 알고리즘이 좀 더 간결하고 자연스럽게 풀리는 경우가 많습니다.

 

 

예시 1 - countDown 

아래는 countDown을 하는 함수입니다. 기본적인 반복문으로 사용하면 아래처럼 쓰일 수 있는데요.

// Iterative Version
function countDown(num){
    for(var i = num; i > 0; i--){
        console.log(i);
    }
    console.log("All done!")
}

 

 

위 코드를 아래처럼 재귀로 바꿔볼 수 있습니다. 

// Recursive Version
function countDown(num){
    if(num <= 0) {
        console.log("All done!");
        return;
    }
    console.log(num);
    num--;
    countDown(num);
}

countDown(3)

// 3
// 2
// 1
// All done!

 

 

 

 

 

예시 2 - sumRange 

다른 예시는 이렇습니다. 

function sumRange(num){
   if(num === 1) return 1; 
   return num + sumRange(num-1);
}

sumRange(3)
    // return 3 + sumRange(2)
    //             return 2 + sumRange(1)
    //                         return 1

 

위의 sumRange는 return에서 자기 자신을 다시 호출하고, num이 1이 될 때까지 계속 반복하다가 1이 되면 비로소 멈추고 마지막 반환값인 1을 return합니다.

주석을 친 부분을 참고하시면 이해가 쉬우실 거에요.

 

 

해당 예시를 snippet으로 돌려보면 아래처럼 call stack에서 sumRange의 호출 흐름을 확인하실 수도 있습니다.

재귀를 사용하실 때는 디버깅을 꼭 해보면 좋을 것 같습니다. 

 

 

 

스택에 함수가 다 호출되었으면, return 1부터 역순으로 돌아가며 계산을 합니다. 

 

1

1+2(3)

3+3(6)

 

이런 순서대로요.

 

 

 

 

 

재귀 함수 사용시 유의점

종료조건이 제대로 되어있지 않으면 끝이 없이 영원히 계속 코드가 돌다가, Maximum call stack경고가 나타날테니 조심하셔야 합니다.  재귀가 계속 될 때 return을 시켜야 명확하게 해당 함수 호출이 종료되는 것을 염두합시다.

 

그리고 우리가 종종 잘 잊는 사항 중 하나는 무엇을 반환하는지 잊는 것인데요. 인자 값으로 어떤 값을 넘길지, 그 값이 반복하고자 하는 수식이 맞는지 확인해야 하겠습니다. 그리고 재귀가 다 끝나면 마지막 값을 반환하는 것도 유념해야 합니다.

 

 

헬퍼 메소드 재귀

헬퍼 메소드 재귀란 재귀와 함께 사용되는 설계 패턴 중 하나입니다. 헬퍼 메소드는 주로 재귀 호출에 필요한 추가 매개변수를 관리하며, 사용자에게는 보이지 않는 내부 함수로 작동합니다.

 

헬퍼 메소드 재귀를 사용하는 이유는 사용자에게 복잡한 인자를 노출하지 않으면서도 필요한 모든 정보를 재귀 함수에 전달할 수 있기 때문입니다. 이 패턴은 특히 초기 매개변수 설정이 복잡하거나 추가적인 상태 관리가 필요한 재귀적 문제 해결에 유용합니다. 우리가 배열이나 데이터 목록 같은 걸 컴파일 해야 할 때 흔히 이렇게 작업을 합니다.

 

 

위 예시에서 result라는 빈 배열을 생성하고 그 안에 모든 데이터를 입력합니다. 그리고 헬퍼 함수를 호출합니다. 이렇게 하면 result를 스코프 밖에 두지 않을 수 있어서, 원하는 정보를 수집하다가 helper(재귀 함수)를 다 호출한 뒤 result를 반환할 수 있게 됩니다. 이런 이유 때문에 데이터 컴파일에 유용하다는 것입니다.

 

 

순수 재귀

function collectOddValues(arr){
    let newArr = [];
    
    if(arr.length === 0) {
        return newArr;
    }
        
    if(arr[0] % 2 !== 0){
        newArr.push(arr[0]);
    }
        
    newArr = newArr.concat(collectOddValues(arr.slice(1)));
    return newArr;
}

collectOddValues([1,2,3,4,5])

 

위와 같은 문제이지만 newArray가 초기화되고 새로운 배열을 받을 때마다 해당 배열을 각각 이어 붙이는(concat사용) 방식도 있습니다. 

 

 

 해당 그림은 위 코드를 시각화 한건데요. 재귀 함수가 다 돌고나면 역순으로 다시 계산을 하면서, 빈 배열 [ ]에 계속 값을 합칠 수 있습니다.  이런 식으로 순수 재귀를 활용하여 문제를 해결할 수도 있습니다.

순수 재귀를 사용할 때는 slice, 스프레드 연산자, concat과 같은 메소드를 사용하여 배열을 변경하지 않고 결과를 축적할 수 있습니다.

 

 

 

 

 

심화 문제 

<reverse>
💬 문자열을 받아들이고 그 문자열의 역순인 문자열을 반환하는 reverse 함수를 작성합니다.

function reverse(){
  // add whatever parameters you deem necessary - good luck!
}

// reverse('awesome') // 'emosewa'
// reverse('rithmschool') // 'loohcsmhtir'

 

 

위 문제는 아래와 같이 풀 수 있습니다.

 

function reverse(str) {
  // 재귀의 종료 조건: 빈 문자열이거나 한 글자만 있는 문자열은 그대로 반환
  if (str.length <= 1) {
    return str;
  }
  // 현재 문자열의 첫 글자를 제외한 나머지 문자열에 대해 reverse 함수를 재귀적으로 호출
  // 그리고 현재 문자열의 첫 글자를 결과 문자열의 끝에 붙임
  return reverse(str.substring(1)) + str.charAt(0);
}

 

이 코드는 다음과 같이 작동합니다:

1. 만약 문자열의 길이가 1 이하라면, 문자열을 그대로 반환합니다. 이는 재귀 호출의 종료 조건입니다.

2.그렇지 않다면, 문자열의 첫 번째 문자를 제외한 나머지 문자열에 대해 reverse 함수를 재귀적으로 호출합니다.

3.마지막으로, 첫 번째 문자를 재귀적으로 반전된 문자열의 끝에 추가합니다. 예를 들어, reverse("hello")는 reverse("ello") + "h"를 호출하게 됩니다. 이것은 다시 reverse("llo") + "e" + "h"를 호출하고, 이 과정이 문자열의 길이가 1 이하가 될 때까지 계속됩니다. 

 

4. 최종적으로, 모든 문자들이 반대 순서로 연결되어 원래 문자열의 역순이 반환됩니다.

 

 

 

 

문법 설명

 

substring()과 charAt()은 JavaScript에서 문자열을 다루기 위해 자주 사용되는 두 가지 메소드입니다.

 

 

substring()

substring() 메소드는 문자열의 특정 부분을 추출하여 새 문자열을 반환합니다. 이 메소드는 두 개의 인덱스를 매개변수로 받으며, 첫 번째 인덱스는 추출이 시작되는 부분을, 두 번째 인덱스는 추출이 끝나는 부분 바로 전을 가리킵니다.

 

var str = "Hello, world!";
var subStr = str.substring(0, 5); // "Hello"

 

이 예제에서 substring(0, 5)는 원본 문자열 str의 첫 번째 문자(인덱스 0에 해당하는 'H')에서 시작해 다섯 번째 문자(인덱스 4에 해당하는 'o')까지의 부분 문자열을 반환합니다.

 

var subStr = str.substring(7); // "world!"

 

substring() 메소드에서 두 번째 인덱스를 생략하면, 문자열의 나머지 부분이 모두 반환됩니다.

 

 

 

 

charAt()

charAt() 메소드는 문자열에서 지정된 위치에 있는 문자를 반환합니다. 이 메소드는 하나의 인덱스를 매개변수로 받으며, 이 인덱스에 해당하는 문자열의 문자를 반환합니다.

 

var str = "Hello, world!";
var char = str.charAt(0); // "H"

 

이 예제에서 charAt(0)은 문자열 str의 첫 번째 문자 'H'를 반환합니다.

만약 charAt()에 주어진 인덱스가 문자열의 범위를 벗어난 경우, 빈 문자열을 반환합니다.