[알고리즘] 재귀(recursion), 재귀함수(recursive function)

재귀(recursion) 및 재귀함수(recursive function), 팩토리얼을 구하는 함수 예제코드

 

1. 재귀

자기자신을 호출한다는 말로 자기자신을 반복해서 돌아간다라는 의미를 가지고 있다.

 

2. 재귀함수

재귀를 하는 함수로 정의 단계에서 자신을 재참조하는 함수를 뜻한다.

 

---

 

재귀함수의 예시로 팩토리얼을 구하는 함수가 있다.

예제코드

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

console.log(factorial(10));

 

1. factorial 함수는 재귀함수로 factorial함수에서 factorial 함수를 또 호출한다. (자기 자신을 호출하는 것이다.)

2. 인자만 함수 내부에서 n에서 n-1로 바뀌게 된다.

3. factorial(3)을 호출하면 내부적으로는 3 * factorial(2)가 호출된다.

4. factorial(2)는 2 * factorial(1)을 호출하고 factorial(1)은 1 * factorial(0)을 호출한다.

5. factorial(0)==1이기때문에 최종적으로 결과는 3 * 2 * 1 * 1 = 6이 된다.

6. 위 3~5의 과정과 같이 factorial(n)의 값을 재귀적으로 계산하여 반환한다.

 

---

 

결론

1. 재귀적으로 푸는 것은 분할 정복 알고리즘(Divide and Conquer Algorithm) 중의 하나이다.

 * 어떤 문제를 한 번에 풀기 힘들 때, 작은 조각으로 쪼개어 푸는 것을 분할 정복 알고리즘라고 한다.
2. 재귀를 사용하는 것은 컴퓨터에게는 많은 부담을 주지만, 개발자의 가독성을 높혀준다.

3. 반복문에 비해 메모리를 많이 차지하기 때문에 성능을 중시한다면 재귀를 쓰지 않는 게 좋다.

4. 재귀는 분할정복 알고리즘, DP 등에서 사용하여 DP를 사용할 때 재귀의 반환값이 보통 메모이제이션된다.

 

2023.06.13 - [개발 용어 정리] - [알고리즘] 메모이제이션(memoization)

[알고리즘] 메모이제이션(memoization)