순환(recursion)이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.
(재귀함수)
예를 들어, 정수의 팩토리얼이 있다.
n! = 1 (n=0), n*(n-1)! (n>=1)
C언어 코드는 다음과 같다.
int factorial(int n)
{
if(n<=1) return(1);
else return (n* factorial (n-1) );
}
기본적으로 반복과 순환은 그 표현 능력이 같으며 많은 경우 , 특히 순환 호출이 끝에서 이루어지는 순환 알고리즘의 경우, 반복 알고리즘으로 바꾸어 쓸 수 있다. 그러나 순환은 어떤 문제에서는 반복에 비해 알고리즘을 훨신 명확하고 간결하게 나타낼 수 있다는 장점이 있다.
그렇다면 순환과 반복 중에서 어떤 형태가 바람직할까? 원래의 정의가 순환적으로 되어 있는 경우, 대개 순환 형태의 코드가 더 이해하기 쉽다. 그러나 순환적인 코드의 약점은 수행시간이다. 그러나 적지 않은 경우에 순환을 사용하지 않으면 도저히 프로그램을 작성할 수 없는 경우가 종종 있다.
순환의 원리는 분할 정복(divide and conquer)이다. 순환은 알고리즘의 정의가 순환적으로 되어 있는 경우에 유리하다. 예를 들어 팩토리얼 함수 계산, 피보나치 수열, 이항계수 계산, 각종 이진 트리 알고리ㅈ즘, 이진 탐색, 하노이 탑 문제들은 순환 알고리즘을 쓰는 것이 자연스러운 알고리즘들이다.
- 거듭 제곱 계산
- 피보나치 수열의 계산
- 하노이탑 문제