Recursion 재귀함수 - Javascript

Recursion이란?

: Function이 스스로를 내부에서 부르게 하여 문제를 해결하는 기술이다. 이렇게 하면 소량의 처리만 완료하고 나머지 문제를 재귀 호출에 위임할 수 있게 된다.

아래의 함수를 보고 고민하여 보자.

var eat = function(meal) {
  console.log('meal before bite:', meal);
  console.log('now eating', meal.pop());
  if(meal.length) {
    eat(meal);
  } else {
    console.log('done with the meal!');
  }
}

위 함수의 결과는 다음과 같다.

eat(['soup', 'potatoes', 'fish']);
// => meal before bite: ["soup", "potatoes", "fish"]
// => now eating fish
// => meal before bite: ["soup", "potatoes"]
// => now eating potatoes
// => meal before bite: ["soup"]
// => now eating soup
// => done with the meal!

meal 배열의 element가 없어질 때까지 함수가 반복적으로 실행되는 것을 알 수 있다.
이제부터 Recursion의 개념을 익히고, 어떻게 적용할 수 있을지, 또한 iteration과는 어떻게 다른지를 알아보자.

Classic Example - Factorial
팩토리얼이란 정수 n에 대하여, 1부터 정수 n까지의 정수를 모두 더한 값을 나타낸다.

-Iterative Way

var factorial =  function(number) {
  var result = 1;
  for (var i = number; i > 0; i--) {
    result *= i;
  }
  return result;
}

-Recursive Way

var factorial = function(number) {
  //number === 0이 base case이다
  if (number === 0) {
    return 1;
  }
  //return (number*factorial(number-1)) 부분이 재귀호출되는 Recursive case이다
  return (number * factorial(number - 1));
}

Recursion은 함수가 끝나는 조건인 Base Case와 재귀호출하는 내용을 담은 Recursive Case로 구성된다.

참고 학습 자료 : https://www.sitepoint.com/implementing-memoization-in-javascript/