Algorithm - Recursion

Recursion

Why use Recursion?

recursion : a process (a function) that calls itself

• recursion을 사용하는 곳
  • JSON.parse / JSON.stringfy
  • document.getElementById / DOM 탐색 알고리즘
  • Object 탐색
  • 복잡한 data structure
  • 반복문의 대체제

Call Stack

• a stack data structure
• 함수를 호출하면 함수의 excute context가 call stack의 최상단으로 푸쉬됨
• return 키워드를 보거나 함수의 코드가 끝까지 실행되면 함수의 excute context가 종료되고 call stack에서 제거됨
• call stack은 LIFO의 실행 순서이므로 call stack의 최상단 excute context가 종료되어 제거될 때까지 다른 context는 실행되지 않음
• recursion 함수를 실행시키면, 함수가 멈출때까지 call stack에 함수의 excute context를 계속 추가시킴

Recursion Function

• base case에 도달할 때까지 다른 input 값의 같은 함수가 실행됨
  • base case : recursion이 끝나는 조건
• recursion function에서 error가 발생하는 경우
  • base case가 없을 때 => stack overflow!
  • return 문이 없거나 잘못된 값을 return했을 때 => stack overlfow!

Helper Method Recursion

• helper method recursion : outer 함수는 recursive하지 않고, inner 함수(helper)가 recursive한 함수

function outer(input) {
  let outerScopedVariable = [];
  
  function helper(helperInput) {
    // modify the outerScopedVaraible
    helper(helperInput--);
  }
  
  helper(input);
  
  return outerScopedVariable;
}

• helper method recursion example

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

Pure Recursion

• pure recursion : helper 함수의 도움 없이 함수 자체가 recursive함
• pure recursion Tips
  • array : slice, spread operator, concat 등의 메서드를 사용하여 array의 복사본을 만들기 (array를 변형시키지 말 것)
  • string : slice, substr, substring 등의 메소드를 사용하여 string의 복사본을 만들기 (string은 immutable함)
  • object : Object.assign, spread operator를 사용하여 object의 복사본을 반들기

• pure recursion example

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

Recursion Problems

Math.pow()

function power(base, exponent){
    if (exponent === 0) return 1;
    return base * power(base, exponent - 1);
}

Factorial

function factorial(num){
   if (num === 0) return 1;
   return num * factorial(num - 1);
}

productOfArray

• 주어진 array의 모든 숫자를 곱한 값을 반환하는 회귀 함수 구현

function productOfArray(arr) {
    let result = 1;
    function helper(helperInput) {
        if (helperInput.length === 0) return;
        result *= helperInput[0];
        helper(helperInput.slice(1));
    }
    
    helper(arr);
    return result;

recursiveRange

• 0에서부터 주어진 숫자까지 더한 값을 반환하는 회귀 함수 구현

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

fibonacci

• 피보나치 수열의 주어진 숫자 번째 수를 반환하는 회귀 함수 구현

function fib(num){
  if (num <= 2) return 1;
  return fib(num - 1) + fib(num - 2);
}