C++ 기초 : 재귀 함수 (2)

---

반복문으로 구현한 Factorial 함수를 

재귀 (Recursion) 함수를 이용해서 구현해 보겠습니다.

 

 

7!은 7 * 6!과 같습니다.

10!은 10 * 9!과 같죠.

규칙성이 보이시나요?

 

수식으로 써 보면 n! = n * (n-1)! 이죠.

 

이러한 규칙성을 적용해서 구현하면 될 것입니다.

 

 

Factorial_Recursion 이라는 이름으로

Factorial 계산을 위한 재귀(Recursion) 함수를 만들었습니다.

 

Factorial_Recursion 함수를 보면

if 문이 있는데 재귀 함수를 탈출하기 위해서 존재합니다.

변수 _iNum의 값으로 1이 들어오면 

더 이상 계산할 필요 없이 1을 반환하고 재귀 함수를 탈출하면 됩니다.

1!은 계산해봤자 1이니까요.

 

 

int iValue3 = Factorial_Recursion(5) 라는 명령을 만나면

 

위 그림처럼  

Factorial_Recursion 함수가 호출되면서 main 함수 위에 쌓일 것입니다. 

Factorial_Recursion 함수의 지역변수 _iNum에는 5가 들어갑니다.

 

 

그리고 5 * Factorial_Recursion(5 - 1),

즉 5 * Factorial_Recursion(4)를 반환하려고 하는 순간

 

Factorial_Recursion(4)를 만났으므로 

먼저 호출된 Factorial_Recursion 함수 위에 Factorial_Recursion 함수가 쌓입니다.

두 번째 Factorial_Recursion 함수의 지역변수 _iNum에는 4가 들어갑니다.

 

 

그리고 4 * Factorial_Recursion(4 - 1),

즉 4 * Factorial_Recursion(3)을 반환하려고 하는 순간

 

Factorial_Recursion(3)을 만났으므로 

두 번째 Factorial_Recursion 함수 위에 Factorial_Recursion 함수가 쌓입니다.

세 번째 Factorial_Recursion 함수의 지역변수 _iNum에는 3이 들어갑니다.

 

 

그리고 3 * Factorial_Recursion(3 - 1),

즉 3 * Factorial_Recursion(2)를 반환하려고 하는 순간

 

Factorial_Recursion(2)를 만났으므로 

세 번째 Factorial_Recursion 함수 위에 Factorial_Recursion 함수가 쌓입니다.

네 번째 Factorial_Recursion 함수의 지역변수 _iNum에는 2가 들어갑니다.

 

 

그리고 2 * Factorial_Recursion(2 - 1),

즉 2 * Factorial_Recursion(1)을 반환하려고 하는 순간

 

Factorial_Recursion(1)을 만났으므로 

네 번째 Factorial_Recursion 함수 위에 Factorial_Recursion 함수가 쌓입니다.

다섯 번째 Factorial_Recursion 함수의 지역변수 _iNum에는 1이 들어갑니다.

 

그런데 if 문에서 _iNum과 1이 같다면 1을 반환하라는 코드를 만납니다.

다섯 번째 Factorial_Recursion 함수의 지역변수 _iNum의 값은 1이므로

1을 반환하고 다섯 번째 Factorial_Recursion 함수가 스택 메모리 영역에서 사라집니다.

 

 

 

 

네 번째 Factorial_Recursion 함수에서

2 * Factorial_Recursion(1)을 반환하려고 했죠?

Factorial_Recursion(1)을 통해 1을 얻었으므로 2 * 1 = 2를 반환하게 됩니다.

이후 네 번째 Factorial_Recursion 함수가 스택 메모리 영역에서 사라집니다.

 

 

 

 

세 번째 Factorial_Recursion 함수에서

3 * Factorial_Recursion(2)를 반환하려고 했죠?

Factorial_Recursion(2)를 통해 2를 얻었으므로 3 * 2 = 6을 반환하게 됩니다.

이후 세 번째 Factorial_Recursion 함수가 스택 메모리 영역에서 사라집니다.

 

 

 

 

두 번째 Factorial_Recursion 함수에서

4 * Factorial_Recursion(3)을 반환하려고 했죠?

Factorial_Recursion(3)을 통해 6을 얻었으므로 4 * 6 = 24를 반환하게 됩니다.

이후 두 번째 Factorial_Recursion 함수가 스택 메모리 영역에서 사라집니다.

 

 

 

 

첫 번째 Factorial_Recursion 함수에서

5 * Factorial_Recursion(4)를 반환하려고 했죠?

Factorial_Recursion(4)를 통해 24를 얻었으므로 5 * 24 = 120을 main 함수에 반환하게 됩니다.

이후 첫 번째 Factorial_Recursion 함수가 스택 메모리 영역에서 사라집니다.

 

 

 

 

main 함수 코드, int iValue3 = Factorial_Recursion(5)에서

Factorial_Recursion(5)를 통해 120을 얻었으므로

변수 iValue3에는 120이 들어가게 됩니다.

 

 

 

 

 

---

 

 

 

 

 

 

다만 위 예시로 재귀 함수의 장점을 느끼긴 힘들죠?

더 나아가서 피보나치 수열과 관련하여 함수를 만들어 보죠.

 

피보나치 수열은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 

바로 앞 두 항의 합인 수열입니다.

 

첫 번째 수와 두 번째 수를 합하면 세 번째 수가 나오고

두 번째 수와 세 번째 수를 합하면 네 번째 수가 나옵니다.

이 규칙을 반복하여 만든 수열이죠.

 

1 1 2 3 5 8 13 21 34 55 · · ·

숫자로 표현하면 위와 같습니다.

 

 

이번에 만들 함수는

함수에 숫자를 넣으면

그 숫자에 해당하는 항의 수를 반환하는 함수입니다.

 

예를 들어 Fibonacci(3)을 하면

피보나치 수열의 세 번째 항인 2를 반환할 것입니다.

 

 

먼저 for 문으로 만들어 봅시다.

 

피보나치 수열에서 n번째 항의 숫자는

(n - 2)번 덧셈을 진행해야 나옵니다.

 

3번째 항의 숫자는 2입니다.

2이라는 숫자는 (3 - 2)번, 즉 1번 덧셈을 진행해야 나오죠.

1 + 1을 해서 1번 덧셈을 진행하면 2라는 숫자가 나옵니다.

 

4번째 항의 숫자는 3입니다.

3이라는 숫자는 (4 - 2)번, 즉 2번 덧셈을 진행해야 나오죠.

1 + 1을 해서 1번 더하면 2가 나오고,

이를 다시 앞의 숫자인 1과 더해서 2번 덧셈을 하면

3이라는 숫자가 나옵니다.

 

넘어가서 7번째 항의 숫자는 13입니다.

13이라는 숫자는 (7 - 2)번, 즉 5번 덧셈을 진행해야 나오죠.

1 + 1을 해서 덧셈을 1번 하면 2가 나오고,

이를 다시 앞의 숫자인 1과 더해서 덧셈을 2번 하면 3이 나오고,

이를 다시 앞의 숫자인 2와 더해서 덧셈을 3번 하면 5가 나오고,

이를 다시 앞의 숫자인 3과 더해서 덧셈을 4번 하면 8이 나오고,

이를 다시 앞의 숫자인 5와 더해서 덧셈을 5번 하면 13이 나옵니다.

 

위 규칙을 바탕으로 for 문의 식을 완성하면 아래와 같습니다.

int Fibonacci(int _iNum)
{
    if ( _iNum == 1 || _iNum == 2)
    {
      return 1;
    }
    
    for (int i = 0; i < _iNum - 2; i++)
    {

    }
}

 

피보나치 수열의 첫 번째 항과 두 번째 항은 1이므로

_iNum의 값이 1이나 2면 1을 반환하라는 if 문이 들어가 있습니다.

 

Fibonacci 함수가 만약 7이라는 숫자를 받으면

for 문이 i가 0부터 시작해서 (7 - 2) 미만일 때까지만 반복하므로 

0, 1, 2, 3, 4 총 5번 덧셈을 반복해서 7번째 항의 숫자를 알아낼 것입니다.

 

 

그렇다면 for 문 중괄호 안에는 덧셈식을 넣어줘야겠죠.

 

피보나치 수열은 계속 앞항의 수와 뒤항의 수를 계속 더해가죠.

 

이를 위해서 앞항의 수를 저장할 변수와 뒤항의 수를 저장할 변수, 

그리고 두 수를 더한 수를 저장할 변수가 필요하겠네요.

 

그림으로 표현하면 아래와 같습니다.

 

앞항의 수를 저장하는 변수 iPrev1과 뒤항의 수를 저장하는 변수 iPrev2,

그리고 두 수를 더한 수를 저장할 변수 iReturnValue를 추가했습니다.

피보나치 수열은 1 1 로 시작하기 때문에 iPrev1과 iPrev2을 각각 1로 초기화하였습니다.

 

 

다음은 어떻게 진행되어야 할까요?

 

두 수의 합을 저장한 변수 iReturnValue의 값이 

뒤항의 수를 저장하는 변수 iPrev2에 대입되고

뒤항의 수를 저장하는 변수 iPrev2의 값이

앞항의 수를 저장하는 변수 iPrev1로 대입되야 할 것입니다.

이후 두 수의 합을 저장한 변수 iReturnValue에는

iPrev1과 iPrev2의 합이 대입되겠죠.

 

위 과정을 그림으로 표현하면 아래와 같습니다.

 

 

 

이 다음도 같은 과정을 반복하겠죠.

 

iReturnValue의 값이 iPrev2에 대입되고 

iPrev2의 값이 iPrev1로 대입되고

iPrev1 + iPrev2의 값이 iReturnValue에 대입될 겁니다.

 

위 과정을 그림으로 표현하면 아래와 같습니다.

 

 

위 내용을 바탕으로 for 문 안의 코드를 작성하면 

int Fibonacci(int _iNum)
{
    int iPrev1 = 1;
    int iPrev2 = 1;
    int iReturnValue = 0;
    
    if ( _iNum == 1 || _iNum == 2)
    {
      return 1;
    }
    
    for (int i = 0; i < _iNum - 2; i++)
    {
        iReturnValue = iPrev1 + iPrev2;
        iPrev2 = iReturnValue;
        iPrev1 = iPrev2;
    }
}

 

위와 같습니다.

 

 

하지만 위 for 문에는 문제가 있습니다.

 

우리가 의도한 것은

 

위 그림과 같이 iReturnValue 값이 iPrev2에 대입되는 동시에

iPrev2의 값이 iPrev1에 대입되는 흐름이지만,

 

컴파일러는 순서대로 정직하게 작동합니다.

 

 

 

위 그림과 같이

iReturnValue 값이 iPrev2에 대입되면서 iPrev2의 값을 2로 덮어씌웁니다.

이후 이 값이 iPrev1에 대입되기 때문에 iPrev1에는 2가 대입되죠.

 

 

이를 해결하려면 아래 코드처럼

iPrev2의 값을 먼저 iPrev1에 대입한 후에

iPrev2에 iReturnValue의 값을 대입하면 되겠죠.

int Fibonacci(int _iNum)
{
    if (_iNum == 1 || _iNum == 2)
    {
        return 1;
    }

    int iPrev1 = 1;
    int iPrev2 = 1;
    int iReturnValue = 0;

    for (int i = 0; i < _iNum - 2; i++)
    {
        iReturnValue = iPrev1 + iPrev2;
        iPrev1 = iPrev2;
        iPrev2 = iReturnValue;
    }

    return iReturnValue;
}

 

그리고 for 문을 빠져나오면

iReturnValue의 값을 반환하며 함수를 종료합니다.

 

 

 

 

---

 

 

 

 

Fibonacci 함수를 재귀 함수로 구현해 보겠습니다.

 

n번째 항의 숫자는

(n - 2)번째 항의 숫자와 (n - 1)번째 항의 숫자를 더한 것이죠?

 

만약 5번째 항의 숫자를 알고 싶다면

(5 - 2)번째 항의 숫자, 즉 3번째 항의 숫자와

(5 - 1)번째 항의 숫자, 즉 4번째 항의 숫자를 더하면 알 수 있겠네요.

 

이 규칙을 바탕으로 코드를 작성해 보면

 

위와 같습니다. 디버깅을 해 보니

피보나치 수열 5번째 항의 숫자인 5가 

변수 iValue에 성공적으로 대입된 것을 확인할 수 있습니다.

 

 

 

 

---

 

 

 

 

 

어떤가요?

같은 Fibonacci 수열 n번째 항의 숫자를 구하는 함수여도

for 문으로 구현했을 때와 재귀 (Recursion) 함수로 구현했을 때의

가독성 차이가 보이시나요? 재귀 (Recursion) 함수의 코드가 훨씬 깔끔하죠.

 

사실 이런 상황보다도 계층구조를 표현할 때 재귀 함수의 효율이 정말 좋습니다.

구현도 더 쉬워지고요.

 

 

그러나 이런 유용한 재귀 함수도 느리다는 단점이 있죠.

이러한 단점을 보완하기 위해 꼬리 재귀 (Tail Recursion) 라는 방법을 사용하기도 합니다.

 

 

 

 

강의 출처 : https://www.youtube.com/watch?v=PFc4g8mxOiI&list=PL4SIC1d_ab-aOxWPucn31NHkQvNPHK1D1&pp=iAQB

 

---