재귀

여민수·2022년 9월 7일

JavaScript algorithm data structure

JS로 이해하는 자료구조와 알고리즘

목록 보기

4/6

재귀란 무엇인가?

재귀란 자기 자신을 호출하는 절차 즉, 자기 자신을 호출하는 함수 $=$ 재귀함수

재귀 함수를 알아야 하는 이유

재귀는 모든 곳에 사용됨
- JSON.parse, JSON.stringify
- document.getElementById와 같은 DOM 순회 알고리즘 역시 재귀 함수로 작성됨
  - DOM은 모든 요소가 중첩된 트리 구조로 되어 있어서 재귀를 사용해서 순회하는 것이 효과적
- Object Traversal
- 위 예시 말고도 나만의 복잡한 자료 구조(트리 or 그래프 순회 등)를 만드는데 사용됨
but, 때로는 재귀를 사용하는 것보다 반복문을 사용해서 구현하는 것이 더욱 깔끔할 수 있음

재귀 함수 작성의 두 가지 핵심 구성요소

종료 조건(base case)
- 종료 조건은 재귀가 멈추는 시점
- 종료 조건이 없다면 재귀함수는 끊임없이 자기 자신을 호출하게 됨
다른 입력 값
- 재귀함수를 호출할 때는 매번 다른 데이터를 가지고 함수를 호출하는 것이 목적
- 같은 입력 값만 반복해서 호출한다면 의미 X

재귀함수 예시

예시 1
```
function countDown(num){
  if(num <= 0){
    console.log("All done!");
    return;
  }
  console.log(num);
  num--;
  countDown(num);
}
```
- num을 입력 받아서 num 값이 0이 될 때 까지 숫자를 1씩 감소하면서 출력하는 함수
- num === 3 일 때
  - print 3 → countDown(2) → print 2 → countDown(1) → print 1 → countDown(0) → print "All done!" → return
예시 2
```
  function sumRange(num){
    if(num === 1)
      return 1;
    return num + sumRange(num - 1);
  }
```
- num을 입력 받아서 num 부터 1까지의 합을 계산하는 함수
- 종료 조건: if(num === 1) return 1;
- num === 3 일 때
  - return 3 + sumRange(2)
  - sumRange(2) ➡︎ return 2 + sumRange(1)
  - sumRange(1) ➡︎ return 1
- 즉, return 3 + (2 + 1) ⟹ 10

호출 스택

대부분의 프로그래밍 언어에는 보이지 않는 곳에서 함수 호출을 관리하는 일종의 데이터 구조가 존재
자바스크립트는 호출 스택이 함수 호출 순서를 관리
함수를 호출하면 호출 스택의 꼭대기에 쌓이게 됨
함수 안에 더 이상 실행할 코드가 없거나 return 키워드를 만나게 되면 컴파일러가 스택의 가장 위에 있는 항목을 제거함
but, 재귀함수는 계속해서 새로운 함수(자기 자신)를 호출 스택에 추가함
- 어느 지점에서 종료되는지 아는 것이 중요!

팩토리얼

팩토리얼은 재귀 함수가 사용되는 가장 고전적인 예시
팩토리얼은 숫자 뒤에 "!" 를 붙여서 표시
ex) $4! → 4 * 3 * 2 * 1$

반복문을 사용한 예시

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

재귀함수를 사용한 예시

  function factorialRecursive(num){
    if(num === 1) // 중단 조건
      return 1;
    return num * factorialRecursive(num - 1); // 다른 입력 값
  }

재귀함수의 잠재적 위험성

종료 조건이 없는 경우
- 재귀함수의 종료조건이 없다면 호출 스택에 계속해서 함수를 쌓게 됨
  → Maximum call size exceeded
return 문이 없거나 잘못된 값을 return하는 경우
- 종료 조건이 있더라도 잘못된 값을 계속해서 반환하게 되면 종료 조건에 도달하지 못하는 경우가 발생할 수 있음
위 두가지 경우 모두 stack overflow가 발생하게 됨!

Helper Method Recursion

앞서 작성한 재귀함수는 모두 single stand-alone function
single stand-alone function은 함수 외부에서 함수를 호출하면 해당 함수는 직접 함수 내에서 자기 자신을 호출함
Helper Method Recursion에는 두가지 함수(외부 함수, 내부 재귀 함수)가 존재
예시
```
  function outer(input){
    var outerScopedVariable = [];
    function helper(helperInput){
      helper(helperInput--);
    }
    
    helper(input);
    
    return outerScopedVariable;
  }
```
- 외부 함수를 호출해서 무언가를 내부로 전달, 외부 함수 안에는 또다른 helper()함수가 정의되어 있고 helper()함수는 재귀적으로 자기자신을 호출함
- 배열이나 데이터 목록 같은 걸 컴파일할 때 흔히 이렇게 작업을 함
- 단순히 리스트에 값을 기록하는 tabulation이 X

Pure Recursion

리스트를 변형하지 않고 새롭게 만든 데이터를 담아 합치는 방식으로 재귀를 구현
- 배열을 복사하는 slice, spread연산자(...), concat 같은 메소드를 사용
- 문자열은 변환이 불가능하므로, slice, substr, substring을 통해 string의 복사본을 만듦
- 객체의 복사본은 Object.assign, spread 연산자를 사용해 복사본을 만듦

예시

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]);