재귀함수 (Recursion) 개념 및 특성

재귀 함수란?

특정 문제를 해결할 때 자신의 메서드를 계속 호출(참조)해 가면서 문제를 해결해 나가는 것!

그런데, 자기 자신을 끝없이 호출하게만 한다면 다음과 같은 현상이 일어난다.

 

https://www.flickr.com/photos/carlberger/7992972355

이것은 마치.. 무한루프???

맞다. 반복문과 마찬가지로 끝 점이 없다면 무한루프에 빠지게 된다.

반복문에서의 무한루프는 반복문을 헤어 나올 수 없다는 것이라면, 재귀 함수에서의 무한루프는 나 자신을 끝도 없이 호출하게 된다. 그래서 Stack Overflow라는 그 유명한 오류가 발생하게 된다.

그렇다면 어떻게 해야 할까?

끝 지점이 있어야 한다.

 

다음의 C 코드를 살펴볼까?

2014년도 계리직 문제 응용

#include <stdio.h>

int sub(int n){
    if(n==0) return 1; //base code
    if(n==1) return 2; //base code
    return (sub(n-1)+sub(n-2)); // Recursive case
}

int main(){
	int a=0;
    a=sub(8);
    return 0;
}

[여담]

생각보다 전산직 공무원 임용시험에서 이러한 문제가 많이 나온다.

필기시험에서는 재귀 함수가 이 정도면 끝이지만, 코딩 테스트에서는 이 정도는 개념 익히기용 기본 수준이라고 생각한다.

적어도 미로 찾기라든지 blob 찾아서 size를 계산하고 개수를 카운트하는 등의 응용 작업들도 할 수 있어야 하니까.

 

---

모든 순환 함수는 반복문으로 변경할 수 있다.

반대로 그 역도 성립할 수 있다고 본다.

순환 함수의 경우에는 복잡한 알고리즘을 단순하게 표현이 가능하다는 이점이 있다.

그러나 함수 호출을 하면서 오버헤드 현상이 일어날 수 있기 때문에 조심해야 한다.

(주로 변수 매개 값들을 전달하거나 액티베이션의 프레임 생성 등의 문제가 이슈가 되곤 한다.)

 

예제로는 많은 것들이 있다.

• 1부터 n까지의 합.
• "!"팩토리얼
• 최대공약수 문제
• 피보나치 계산하기
• 문자열의 길이를 구하는 등의 응용문제
• 2진수 변환하기 문제
• 배열 총합