[순환과 반복] 팩토리얼 계산 프로그램

팩토리얼을 순환, 반복 개념에 맞추어서 프로그램을 짜면 다음과 같다.

 

1. 순환

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int factorial(int n)
{
    cout << n << "\n";
    if (n <= 1)
    {
        return n;
    }
    else
    {
        return (n * factorial(n - 1));
    }
}

int main() 
{
    int k = factorial(8);
    cout << k;
    return 0;
}

출력

8
7
6
5
4
3
2
1
40320

스택 호출에 따라(뒤에 호출된 함수부터 리턴)

        return (n * factorial(n - 1)); 순서대로

return (1 * 1);

return (2 * 1);

return (3 * 2);

return (4 * 6);

return (5 * 24);

return (6 * 120);

return (7 * 720);

return (8 * 5040) = 40320 이 된다. 

 

위와 같이 프로그램을 작성하면,(프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출)

사실상 다른 함수를 호출하는 것과 동일하다.

복귀 주소가 시스템 스택에 저장되고

호출되는 함수를 위한 매개변수와 지역 변수를 스택으로부터 할당받는다.

이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드라고 한다.

 

호출된 함수가 자기 자신이므로 자기 자신의 시작 위치로 점프하여 수행을 시작한다.

호출된 함수가 끝나게 되면 시스템 스택에서 복귀 주소를 추출하여 호출한 함수로 되돌아가게 된다.

순환호출이 계속 중첩될수록 시스템 스택에는 활성레코드들이 쌓이게 된다.

 

함수호출마다 새로운 지역변수를 만들 수 있기에 순환호출이 가능하다.

 

이와 같은 순환 알고리즘은 

자기 자신을 순환적으로 호출하는 부분과 순환호출을 멈추는 부분으로 구성되어 있다.

만약 순환 호출을 멈추는 부분이 없다면 시스템 스택을 다 사용할 때까지 순환적으로 호출되다가 결국 오류를 내면서 멈출 것이다. 따라서 반드시 순환 호출에는 순환 호출을 멈추는 문장이 포함되어야 한다.

 

2. 반복

일반적으로 순환은 함수 호출을 하게 되므로 반복에 비해 수행속도 면에서 떨어진다.

아래와 같이 반복 프로그램으로 변경할 수 있다. 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int factorial(int n)
{
    int i, result = 1;
    for (i = 1; i <= n; i++)
    {
        cout << i << "\n";
        result = result * i;
    }
    return result;
}

int main() 
{
    int k = factorial(8);
    cout << k;
    return 0;
}

1
2
3
4
5
6
7
8
40320

 

 

<정리>

순환은 알고리즘의 정의가 순환적으로 되어 있는 경우에 유리하다.

팩토리얼 함수, 피보나치 수열, 이항계수 계산, 이진 트리 알고리즘, 이진 탐색, 하노이 탑 문제들은 순환 알고리즘을 쓰는 것이 자연스러운 알고리즘들이다.