[순환] 순환구조 반복문 순환문 이용해서 구현하기 (ft. 팩토리얼, 피보나치수)

[순환] 순환, 반복

- 순환 알고리즘과 반복문을 이용한 순환구조에 관하여 -

ㅣ순환(recursion) : 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법

ex1) 정수의 팩토리얼

위의 정의에서 팩토리얼 n! 을 정의하는 데 다시 팩토리얼 (n - 1)! 이 사용되었다.

이러한 정의를 순환적이라 하고, 팩토리얼을 구현하는 함수를 만들어보면 다음과 같다.

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

if문 안에 (n <= 1) 이라는 조건을 넣은 이유는 n = 1일 때, 1 * 0! = 1 이며, n < 1 일 경우엔 n! = 1 이기 때문이다.

바로 이 함수처럼 factorial 함수 안에 자기 자신을 또 호출하는 구문을 순환문이라고 한다.

다음으로 반복문을 이용해 팩토리얼을 구현하는 함수를 만들어보자.

int factorial(int n)
{
    int factorial_ans = 1;
    while (n > 1)
    {
        factorial_ans *= n;
        n--;
    }
    return factorial_ans;
}

이런 식으로 반복문으로도 순환 구조를 만들 수 있다. (모든 순환구조를 반복문으로 구현하기는

힘들 수 있다.)

하지만 경우에 따라 반복문을 사용하기 까다로운 문제들이 있을 수 있으므로 문제를 잘 파악하여 

순환문, 반복문을 선택하는 것이 굉장히 중요하다.

또한 효율성도 따져야 하는데 이것은 다음 예시를 들어보며 알아보자.

ex2) 피보나치 수열

순환구조 하면 빼놓지 않고 나오는 문제가 바로 피보나치 수열이다.

실제로 정보처리기사 시험문제로도 출제가 되기도 할 만큼 중요하다.

피보나치 수열은 다음과 같이 정의되는 수열이다.

즉, 일반적인 경우 앞의 두 개의 숫자를 더해서 뒤의 숫자를 만들면 된다.

수열은 다음과 같다 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

피보나치 수열은 정의 자체가 순환적으로 되어 있는것을 알 수 있다. 따라서 구현 시 순환문을 많이 사용할 것이다.

순환문을 이용해 피보나치 수열 계산 함수를 만들어보면

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

다음과 같이 단순하게 나오지만 비효율적인 함수이다.

예를 들어 fibonacci(6) 을 호출한다고 하면

fibonacci(4) 는 2번, fibonacci(3)는 3번 계산되는 등 fibonacci(6)을 구하기 위해 이 함수가 총 25번이나 호출되기 때문이다.

이러한 이유 때문에 피보나치 수열을 계산할 때는 반복문을 이용하는 게 가장 좋은 결과를 얻을 수 있다.

int fibonacci(int n)
{
    if (n < 2) return n;        //예외 처리 n = 0, 1일 때
    else
    {
        int i = 2, fib_res = 1, sumi = 0, tmp;        //피보나치 수열은 앞의 두 개의 숫자를 더해가며 만들어지는 수열
        while (i <= n)
        {
            tmp = fib_res;                    //tmp : 수 옮기기 위한 변수이자 더해지기 이전의 값 저장할 변수
            fib_res += sumi;                //fib_res : 더해지는 결과,  sumi : 더해지는 두 개의 수 중 작은 값
            sumi = tmp;                        // 더해지기 이전 fib_res 즉, 작은 값 sumi 변수에 옮기기
 
            i++;
        }
        return fib_res;
    }
}

이해하기 복잡하지만 피보나치 수열 결과값인 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...  수열을 이해한다면 훨씬 수월할 것이다.

예를 들어 fibonacci(5) 함수를 호출한다면

        

이와 같이 값이 더해지는 과정을 볼 수 있다.