[C++] 재귀 함수 (Recursive Function)

Recursive function, 재귀함수는 '스스로를 호출하는 함수' 입니다.

스스로를 호출하는 방법은 직접 호출할 수도 있고, 다른 함수를 통해 간접 호출할 수도 있습니다.

재귀함수는 이진탐색, 팩토리얼 연산, 피보나치 수열 등 수학이나 데이터를 다루는 분야에서 자주 사용됩니다.

---

 

첫번째로 팩토리얼(!)의 예시를 들어보겠습니다.

우선 팩토리얼이란, '그 수보다 작거나 같은 모든 양의 정수의 곱' 입니다. 

0! = 1 이고, n! = n * (n - 1)! 이라고 이해하면 됩니다.

 

그 함수는 다음과 같이 재귀함수를 활용하여 구현할 수 있습니다.

// factorial function
unsigned long long factorial(unsigned long long n) {
  if (n == 0)
    return 1;
  return n * factorial(n - 1);
}

unsigned long long 인자를 받아서 반환하는 factorial 함수 내부에서,

n이 0이 아닐 때에는 factorial 함수 스스로를 다시 부르는 것이 확인됩니다.

이것이 바로 재귀함수 입니다.

---

 

다음 예시는 피보나치 수열입니다.

피보나치 수열에 대한 설명은 다음 링크를 참조해주세요.

피보나치 수 - 위키백과, 우리 모두의 백과사전

 

 

피보나치 수열 역시 재귀함수를 통해 구현이 가능합니다.

unsigned long long fibonacci(unsigned long long n) {
    if (n <= 1)
    	return n;
    return fibonacci(n - 2) + fibonacci(n - 1);
}

int main(){
    cout << fibonacci(30) << endl;	// 83240
    return 0;
}

---

 

주의 사항

재귀 함수는 유용하게 사용될 수 있는 중요한 함수입니다. 

하지만, 함수 내에서 스스로를 다시 호출하는 만큼 주의해야 할 점들이 존재합니다.

대표적으로는 무한 반복 문제가 있습니다.

적절한 base case를 통한 매커니즘을 구축하지 않으면 무한 반복 함수가 됩니다.

 

또한 재귀 함수로 구현 가능한 모든 함수는 반복문으로도 구현이 가능합니다.

Stack overflow error를 방지하기 위해서는 재귀 함수의 남용을 자제해야 합니다.

 

당연하게도 위의 피보나치 수열과 같은 재귀함수는 함수 호출의 수가 입력값의 상승과 함께 지수적으로 증가합니다.

이와 같이 재귀 함수는 꽤나 자원(메모리)을 크게 소모하는 함수입니다.

유의하여 적절한 상황에만 사용해야 합니다.

 

---