[JS 알고리즘 - 재귀5] 순수 재귀

아래 강의를 듣고 내용을 정리한 포스트 입니다.

https://www.udemy.com/course/best-javascript-data-structures/

이번 포스트는 이전내용과 이어집니다

https://yoonocean.tistory.com/64

[JS 재귀 - 4] 헬퍼 메소드 재귀

 

지난 헬퍼메소드 재귀에서 예시로 들었던 문제를 다른 방식으로 접근해보겠습니다.

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([1,2,3,4,5,6,7,8,9])

 

헬퍼 메소드 재귀가 한가지 전략 이기는 했지만 유일한 방법은 아닙니다. 순수 재귀를 사용해서 같은 작업을 수행할수 있습니다.

순수 재귀는 필요한 모든 코드가 함수 자체에 포함되며, 재귀적입니다.

함수 외부 데이터 구조를 사용하지 않습니다.

중첩된 함수를 사용해서 헬퍼 메소드 재귀를 수행하는게 아닙니다.

좀더 까다로울수 있지만, 순수 재귀만을 이용해 문제를 풀수 있습니다.

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]) // [1,3,5]

위 코드에서는 함수를 호출할때마다 newArr 변수를 정의하고 있습니다.

여기에서 newArr 배열은 실제로 리셋됩니다. 하지만 배열이 리셋되도 상관이 없습니다.

여기서 실제로 하는 작업은 계산이 완료 됐을때 모든 배열을 하나의 배열로 합쳐서 반환합니다.

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

이런식으로 마지막에 도달할때 까지 concat 되는 배열을 반환하다가, 재귀가 끝나면 콜스택에서 하나씩 실행되며 결국 [1,3,5] 를 반환하게 됩니다.

순수 재귀 팁

- 배열을 사용하고 헬퍼 메소드없이 순수 재귀를 사용할때, 배열을 복사하는 slice, spread 연산자, concat 등의 메소드를 사용할수 있습니다. 배열을 변경할 필요가 없어집니다. 일종의 결과 축적을 할수 있습니다.

- 문자열은 변경할수가 없습니다. 그래서 slice 나 substring 을 사용해서 사본을 만들어야 합니다.

- 객체의 경우, Object.assign 이나 spread 연산자를 사용하는게 유용합니다.