Recursion 정의 + 예제

재귀함수란 ?

 

함수는 함수 안에서 자기 자신을 다시 호출하는 것.

 

재귀함수를 사용하는 이유

 

1. 알고리즘 자체가 재귀적으로 표현할 때 가독성이 좋다.
2. 변수 사용을 줄여 준다.

 

재귀함수의 단점

 

메모리를 많이 차지하며 성능이 반복문에 비해 느리다.

 

 

재귀함수의 사용예제

 

Factorial

1부터 정수 n까지의 정수를 모두 곱하는 것.

반복문을 사용한 factorial 

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

// factorial(5) 의 경우 i는 1,2,3,4,5 이므로 1*2*3*4*5 = 120.


재귀함수를 사용한 factorial

function factorial(number) {
  if(number == 1) {
    return number;
  } else {
      return number * factorial(number-1);
    }
}

// factorial(5) 의 경우 5 * factorial(4)
// 다시 factorial(4) 가 실행 , factorial(5) * factorial(4) * factorial(5) ...
// 1이되면 종료.

fibonacci
0, 1로 시작해서 다음 수는 앞의 두 수의 합이 된다. Ex) 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 

var fibonacci = function(number) {
  if (number < 2) {
    return number;
  } else {
    return fibonacci(number - 1) + fibonacci(number - 2);
  }
};