: 어떤 사건이 자기 자신을 포함하고, 다시 자기 자신을 사용하여 정의될 때 재귀적 이라고 함.
재귀를 사용한 순차곱셈(팩토리얼)
#include<stdio.h>
int factorial(int n){
if(n>0) return n*factorial(n-1); // 재귀호출
else return 1;
}
int main(){
int x;
printf("input integer: ");
scanf("%d",&x);
printf("%d factorial is %d",x,factorial(x));
return 0;
}
위의 팩토리얼 함수와 같이 자기 자신(함수)를 직접적으로 호출하는 방법을 직접재귀, 함수a가 함수b를, 함수b가 함수a를 호출하는 방법을 간접재귀라고 한다.
두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법
유클리드 호제법을 사용한 문제
직사각형을 정사각형으로 완전히 채웁니다. 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하시오
int gcd(int x,int y){
if(y==0) return x;
else return gcd(y,x%y);
}
void recur(int n){
if(n>0){
recur(n-1);
printf("%d\n",n);
recur(n-2);
}
}
// 1 2 3 1 4 1 2
가장 위쪽에 위치한 함수 호출부터 시작해 계단식으로 자세히 조사해가는 방법
아래쪽부터 쌓아올리며 분석하는 방식
recur 함수(n-2)는 다음과 같다.
n의 값을 n-2로 업데이트하고 처음 지점으로 돌아간다.void recur(int n){ Top: if(n>0){ recur(n-1); printf("%d\n",n); n=n-2; goto Top; } }
재귀의 제거는 스택을 사용하여 해결가능. 지난 스택정리 부분의 IntStack.c와 IntStack.h 사용
void recur(int n){ IntStack stk; Initialize(&stk, 100); Top: if(n>0){ Push(&stk,n); n=n-1; goto Top; } if(!IsEmpty(&stk)){ Pop(&stk,&n); printf("%d\n",n); n=n-2; goto Top; } Terminate(&stk); }