[알고리즘] 2.재귀함수

1. 재귀함수란?

함수 내부에서 자기 자신을 호출하는 함수.
재귀함수를 활용하면 문제를 더 작고 해결 가능한 하위 문제로 분할할 수 있기 때문에 보다 직관적이고 간결하게 표현할 수 있다.

2. 일반 함수와 Call Stack 비교

1. 일반 함수
   • 함수가 호출되면 해당 함수의 정보(지역 변수, 반환 주소 등)가 호출 스택에 추가.
   • 함수의 실행이 완료되면 호출 스택에서 해당 함수의 정보가 제거.
   • 호출 스택은 후입선출(LIFO, Last-In-First-Out) 구조를 가지므로, 가장 최근에 추가된 함수의 정보가 먼저 제거.

function eatBreakfast(){
    let meal = cookFood();
    return `Eating ${meal}`
}
function cookFood(){
    let items = ['Meat', 'Egg', "Bread"];
    return items[Math.floor(Math.random()*items.length)];
}

function wakeUp(){
    eatBreakfast();
    console.log("Ok ready to go");
}
wakeUp();

2. 재귀 함수
   • 재귀 함수가 호출되면 호출 스택에 해당 함수의 정보가 추가.
   • 재귀 함수는 호출 스택에 새로운 함수 정보를 추가하므로, 호출 스택에 여러 개의 같은 함수 정보가 중첩될 수 있다.
   • 재귀 함수는 기본 단계(base case)에 도달하여 재귀 호출을 멈추게 되면, 호출 스택에서 해당 함수 정보가 하나씩 제거되면서 이전 호출 스택으로 되돌아간다.

  function countDown(num){
    if(num <= 0){
      console.log('done');
      return;
    }
    console.log(num);
    num--;
    countDown(num)
  }
countDown(5);

요약하자면, 일반 함수는 호출 스택에 함수 정보가 추가되고 제거되는 단순한 방식으로 동작하지만, 재귀 함수는 재귀 호출에 따라 호출 스택에 새로운 함수 정보가 추가되고 제거되는 방식으로 동작한다.

2-1. 재귀함수 Call Stack 예시

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

sumRange(3);

1. sumRange(3) 호출
   | sumRange(3) |

2. 3 + sumRange(2) 실행, sumRange(2) 호출
   | sumRange(2) |
   | sumRange(3) |

3. 2 + sumRange(1)를 실행, sumRange(1) 호출
   | sumRange(1) |
   | sumRange(2) |
   | sumRange(3) |

4. sumRange(1)이 1을 반환, call stack 제거
   | sumRange(2) |
   | sumRange(3) |

5. sumRange(2)는 sumRange(1)의 반환 값을 받아 2 + 1을 반환, callstack 제거
   | sumRange(3) |

6. sumRange(3)은 sumRange(2)의 반환 값을 받아 3 + 3을 반환, callstack 제거
   | (empty) |

3. 헬퍼 메소드

함수가 호출된 이후에도 변수가 값을 유지하게 하는 방법!
함수 위에 let result = [] 같이 뜬금없는 변수를 배치하는 대신, 헬퍼 메소드 재귀를 사용해서 전체를 감싸준다.

function collectOddValues(arr){
  let result = [];
  function helper(input){
    if(input.length === 0){ // 종료 조건
      return;
    }
    if( input[0] % 2 !== 0){
      result.push(input[0]);
    }
    helper(input.slice(1));
  }
  helper(arr);
  return result;
}
collectOddValues([1,2,3,4,5,6])

4. 순수 재귀

모든 코드가 함수 자체에 포함되며 재귀적.

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;
}

5. 재귀 함수를 사용할 때 유의할 것

• 배열을 사용하고 헬퍼 메소드 없이 순수 재귀를 작성하는 경우에 slice, spread 연산자, concat 같은 메소드를 사용한다.
• 문자열은 변경할 수 없기 때문에 slice, substring을 사용해서 사본을 만든다.
• 객체의 경우 Object.assign, spread 연산자를 사용하는 게 유용하다.