[알고리즘] 순환(recursion)

순환(recursion)

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

 

• ex 1) 팩토리얼

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

factorial(3)을 하면, else return 3*factorial(3-1)이 수행되면서 factorial(2)를 호출한다.

factorial(2)에서 else return 2*factorial(2-1)이 수행되면서 factorial(1)를 호출한다.

factorial(1)에서 if (n<=1) return 1;이되면서 1을 반환하면서 순환 호출이 종료된다.

 

즉, factorial(3) = 3*factorial(2)

                   = 3*2*factorial(1)

                   = 3*2*1

                   = 6

 

순환 알고리즘은 이와같이 직관적이며 명확하다는 장점이 있지만 함수 호출을 하기 때문에 시간 복잡도 면에서 비효율적이라는 단점이 있다.

 

※ 분할 정복 기법(divide and conquer) : 문제를 더 작은 동일한 문제로 분해하여 해결하는 방법 -> 위와같이 다른 함수에게 문제를 해결하는 과정을 위임함

 

위 프로그램의 시간 복잡도는 한 번의 곱셈 연산이 이루어지지만 n번 순환 호출하므로 O(n)이다.

 

 

순환 알고리즘의 구조

순환 알고리즘은 반드시 순환 호출을 하는 부분과 멈추는 부분으로 구성되어야한다.

위의 팩토리얼 프로그램에서는 if (n<=1) return 1;이 멈추는 부분이고, else return n*factorial(n-1)이 순환 호출을 하는 부분이다.