- 순환(recursion) 이란?
어떤 알고리즘이나 함수가 자기자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.
- 순환 알고리즘의 구조
- 순환을 멈추는 부분 (탈출 조건)
- 순환 호출을 하는 부분
- 순환 호출의 내부적 구현
먼저 함수 호출의 과정을 살펴보자. 하나의 함수가 자기 자신을 다시 호출하는 것은 다른 함수를 호출하는 것과 동일하다. 즉, 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역변수를 스택으로부터 할당받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성레코드(activation record)라 한다. 순환 호출이 계속 중첩될 수록 시스템 스택에는 활성 레코드드들이 쌓이게 된다.
일반적으로 순환은 함수 호출을 하게 되므로 반복에 비해 수행속도 면에서는 떨어진다.
- 순환을 이용한 팩토리얼 계산 프로그램 n!
- 알고리즘
int factorial ( int n ){
if( n<=1 ) // 탈출조건
return 1;
else
return n*factorial(n-1); // 순환 호출 부분
}
- 피보나치 수열의 계산
0 1 1 2 3 5 8 13 21 34 55 89 ,,,
- 알고리즘
int fib(int n){
if(n==0) return 0;
else if( n==1 ) return 1;
else return ( fib(n-1) + fin(n-2) );
}
- 하노이탑
조건 1. 한 번에 하나의 원판만 이동할 수 있다.
2. 맨 위에 있는 원판만 이동할 수 있다.
3. 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다.
4. 중간의 막대를 임시적으로 이용할 수 있으나 아의 조건들을 지켜야 한다.
- 알고리즘
// 막대 from에 쌓여 있는 n개의 원판을 막대 tmp를 사용하여 막대 to로 옮긴다
void hanoi_tower ( int n, char from, char tmp, char to ){
if(n==1){
from 에서 to로 원판을 옮긴다.
}
else {
1. from의 맨 밑의 원판을 제외한 나머지 원판들을 tmp로 옮긴다.
2. from에 있는 한 개의 원판을 to로 옮긴다.
3. tmp의 원판들을 to로 옮긴다.
}
}
