[알고리즘] 재귀 (자바스크립트)

0. 재귀

• 자기자신을 호출하는 절차 (함수)
• JSON()의 파싱이나, DOM getElementById 등의 내부 코드가 재귀로 구성되어 있음
• 물론 반복문만으로도 구현이 가능하지만, 재귀를 사용함으로써 직관적이고 간결하게 구현할 수 있음

 

1. 필수 요소

중단점 (Base Case)

재귀가 중단되는 시점, 즉 종료 조건과 마지막으로 반환할 Return을 지정해주어야 한다.

 

다른 입력값 (Different Input)

매번 같은 함수를 호출하면서 다른 출력을 반환할 수 있게 하기 위해선 입력값 또한 달라져야 한다.

 

 

2. 예시

예시 반복문을 이용한 팩토리얼 구현

function loopFactorial(num){
  let total = 1;
  for(let i = num;i>0;i--){
    total *= i
  }
  return total
}

 

예시 재귀함수를 이용한 팩토리얼 구현

function recursionFactorial(num){
  if(num===1) return 1
  return recursionFactorial(num-1)*num
}

 

 

3. 설계 패턴

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

재귀 함수와, 그 겉을 둘러싸는 외부 함수로 구성된다. 빈 배열에서 입력값을 핸들링하는데, 이를 외부 함수에 두어 호출될 때마다 초기화되는 것을 방지한다.

 

리스트 인풋 처리에 최적화된 패턴인 듯. 추후 학습할 그래프 이론에서도 사용된다고 한다.

 

예시 헬퍼 메서드 재귀 패턴을 이용한 홀수 필터 구현

function oddValues(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;
}

 

예시 순수 재귀를 이용한 홀수 필터 구현

function oddValues(arr){
    let newArr = [];

    if(arr.length === 0){
        return newArr;
    }

    if(arr[0] % 2 !== 0){
        newArr.push(arr[0]);
    }

    newArr = newArr.concat(oddValues(arr.slice(1)));
    return newArr;
}

---

Javascript 알고리즘 / 자료구조 마스터 (유데미) 강의 수강 후 복습하며 정리한 내용입니다. 원 강의는 이곳에서 수강할 수 있습니다.