[7]

1.재귀

: 어떤 사건이 자기 자신을 포함하고, 다시 자기 자신을 사용하여 정의될 때 재귀적 이라고 함.

재귀를 사용한 순차곱셈(팩토리얼)

#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;
}

2. 직접재귀와 간접재귀

위의 팩토리얼 함수와 같이 자기 자신(함수)를 직접적으로 호출하는 방법을 직접재귀, 함수a가 함수b를, 함수b가 함수a를 호출하는 방법을 간접재귀라고 한다.

3. 유클리드 호제법

두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법

유클리드 호제법을 사용한 문제

직사각형을 정사각형으로 완전히 채웁니다. 이렇게 만들 수 있는 정사각형의 가장 긴 변의 길이를 구하시오

int gcd(int x,int y){
        if(y==0) return x;
        else return gcd(y,x%y);
}

4. 재귀 알고리즘의 분석

void recur(int n){
	
	if(n>0){
		recur(n-1);
    	printf("%d\n",n);
    	recur(n-2);
    } 
}
// 1 2 3 1 4 1 2  

4-1. 상향식 분석

가장 위쪽에 위치한 함수 호출부터 시작해 계단식으로 자세히 조사해가는 방법

4-2. 하향식 분석

아래쪽부터 쌓아올리며 분석하는 방식

5. 재귀 알고리즘의 비 재귀적 표현

5-1. 꼬리 재귀의 제거

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;
        }
}

5-2. 재귀의 제거

재귀의 제거는 스택을 사용하여 해결가능. 지난 스택정리 부분의 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);
}

<재귀 정리된 글>
https://rok93.tistory.com/entry/Do-it-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%ED%95%A8%EA%BB%98-%EB%B0%B0%EC%9A%B0%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%85%EB%AC%B8-%EC%9E%AC%EA%B7%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98