C언어 재귀함수와 피보나치 수열

<재귀함수란>

 

함수가 자기 자신을 호출하는 것입니다. 재귀함수를 이용하면 반복문 없이 반복적인 작업을 수행하는 함수를 구현할 수 있습니다.

c언어에서도 재귀함수를 구현할 수 있는데 , c언어에서는 함수가 자기 자신을 호출할 때, 함수의 호출 스택을 사용하여 재귀적으로 호출됩니다.

 

<재귀함수의 특징>

 

1. 함수가 자기 자신을 호출합니다.

2. 종료 조건이 필요합니다. (없다면 무한루프에 빠집니다.)

3. 호출 스택을 사용합니다. 호출될 땜다 호출 스택에 현재 함수의 상태를 저장하고, 반환할 때마다 호출 스택에서 이전 함수의 상태를 복원합니다.

4. 메모리를 많이 사용할 수 있습니다. 3번과 같이 동작하여 호출 스택의 크기가 커질 수 있기 때문입니다.

5. 코드가 간결합니다. 알고리즘에서 재귀함수를 사용하면 코드가 간결해지는 경우가 있습니다.

 

<재귀함수의 장단점>

 

장점 : 

- 반복문을 사용하는 것보다 재귀함수를 사용하는 방법으로 구현하면 코드가 간결해질 수 있습니다.

- 몇 알고리즘은 재귀함수로 표현하는 것이 간단하고 명확하여 알고리즘을 이해하기 더 쉬워집니다.

 

단점 : 

- 호출 스택 크기에 제한이 있어 호출 스택이 커질 수 있습니다. 따라서 사용할 떄 메모리 사용량에 주의해야 합니다.

- 실행 속도가 느릴 수 있습니다. 함수 호출에는 오버헤드가 발생하므로 반복문을 사용하는 것보다 실행 속도가 느릴 수 있습니다.

- 종료 조건을 정확하게 설정해야 합니다. 그렇지 않으면 무한루프에 빠지게 됩니다.

 

<재귀함수의 동작원리>

 

1. 함수가 호출되면 호출 스택에 현재 함수의 정보(지역변수, 매개변수, 반환주소 등)을 저장

2. 자기 자신을 다시 호출 -> 호출 스택에 새로운 함수 정보 추가

3. 종료 조건이 만족될 때까지 1, 2과정을 반복

4. 반환 값이 있는 경우, 호출 스택에서 이전 함수의 반환값에 저장 -> 반환 값을 사용하여 다음 연산 수행

 

<피보나치 수열>

 

재귀함수를 사용하는 대표적인 알고리즘으로는 피보나치 수열이라는 것이 있습니다.

 

피보나치 수열은 앞의 두 수를 더하여 다음 수를 만들어가는 수열로, 0과 1로 시작합니다.

 

즉, 0,1,1,2,3,5,8,13,21,34, ... 와 같이 이어집니다.

 

피보나치 수열을 구하는 가장 대표적인 방법이 재귀함수를 이용하는 것입니다. 

 

int num(int n) {
    if (n == 0) return 0;
    else if (n == 1) return 1;
    else return num(n-1) + num(n-2);
}

 

c언어로 피보나치 수열을 구하는 코드입니다. 이 함수는 인자로 피보나치 수열에서 몇 번째 수를 구할 지 int n으로 받습니다.

만약 n이 0이라면 0을 반환하고 1이라면 1을 반환합니다. 그외의 경우에는 n-1 과 n-2를 인자로 하는 함수를 재귀적으로 호출하여 두 결과를 더한 값을 반환합니다.

 

만약 int n에 5를 입력했다면 

 

num(5) = num(4) + (3)

num(4) = num(3) + num(2)

num(3) = num(2) + num(1)

num (2) = num(1) + num(0)

 

이고, 각각 값을 대입하면

 

num(2) =  num(1) + num(0) = 1+0=1

num(3) = num(2) + num(1) = 1+1=2

num(4) = num(3) + num(2) = 2+1=3

num(5) = num(4) + num(3) = 3+2=5

 

따라서 num(5)는 5가 됩니다.