[자료구조] 순환 (Recursion)

순환 (Recursion)

흔히 재귀라고 부른다. 즉, 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 순환으로 구현할 수 있는 알고리즘의 대다수는 반복으로도 구현할 수 있다. 다만 순환은 단순하지만 반복이 복잡해지거나, 그 반대가 되는 알고리즘이 존재한다.

 

순환의 예

팩토리얼

팩토리얼은 다음과 같이 정의된다.

 

 

n!을 정의하는 와중에 (n-1)!이 필요하므로, 순환으로 해결할 수 있다. 간단하게 코드로 구현해 보자.

참고로 팩토리얼의 경우에는 순환보다 반복이 빠르다고 알려져 있다.

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

만약 factorial(3)이 들어간다 가정하면, 사진처럼 순서대로 실행될 것이다.

이와 같이 문제를 해결하는 와중에 문제의 일부를 해결한 다음 나머지 문제에 대해서 순환 호출을 한다는 것을 유의해야 한다. 즉, 주어진 문제를 더 작은 동일한 문제들로 분해하여 해결하므로 분할정복(Divide and Conquer)이라고 말할 수도 있다. 분할정복에 대해선 이후에 다시 포스팅을 할 기회가 있을 것이다.

 

이렇게 순환을 사용하면 간단해지는 알고리즘에는 위와 같은 팩토리얼이 있고, 피보나치 / 이항계수 / 이진 트리 / 이진 탐색 / 하노이탑 등등 여러 알고리즘이 존재한다.

 

거듭제곱값 계산

위의 팩토리얼이 반복이 순환에 비해 빨랐다면, 이번 알고리즘은 순환이 반복에 비해 빠르다.

을 계산하는 알고리즘을 구현해보자.

double power(double x, int n)
{
    if (n == 0)
        return 1;
    else if ((n % 2) == 0)
        return power(x * x, n / 2);
    else
        return x * power(x * x, (n - 1) / 2);
}

의 공식을 이용해 n이 짝수이면 x * x을 먼저 계산하고 n/2제곱을 하는 식의 알고리즘이다.
이를 반복으로 구현하면 O(n)의 시간복잡도를, 순환으로 구현한다면 O(log2n)의 시간복잡도를 가진다고 알려져 있다.

 

피보나치

피보나치를 순환으로 구현한다면 가독성도 엄청나게 좋아지고 아주 단순하게 작성이 가능하지만, 수가 커질수록 호출이 과도하게 많이 일어난다는 문제가 있다. 이는 동적 계획법(Dynamic programming)으로 해결 가능하며, 이도 후에 포스팅 할 기회가 있을 것이다.

 

구현하면 다음과 같다.

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

 

가볍게 언급하고 넘어가자면, 다음 사진과 같이 같은 함수를 여러번 반복해서 호출하다보니 시간이 과도하게 걸린다.