ackermann

#include <stdio.h>
int recursive_ackermann(int m, int n) {
	if (!m)
		return n + 1;
	else if (!n)
		recursive_ackermann(m - 1, 1);
	else
		recursive_ackermann(m - 1, recursive_ackermann(m, n - 1));
}

int loop_ackermann(int m, int n) {
    int stack[1000], top = 0, current = 0;
    stack[0] = m;

    while (top >= 0) {
        current = stack[top]; //현재 top이 가르키고 있는 값
        if (current == 0) // 그 값이 만약 0이라면
        {
            n++; // n을 n+1로 업데이트
            top--; //top를 한칸 뒤로 옮김
        }
        else if (n == 0) {
            n = 1;
            stack[top] = current - 1;
        }
        else{
            n--; //n을 n - 1로 업데이트
            stack[top] = current - 1; //지금 top칸을 m - 1로 업데이트
            stack[++top] = current; //그 다음 top칸을 m으로 업데이트
        }        
    }
    return n;

}

int main(int argc, char* argv[]) {
	int m,n;
	scanf_s("%d %d", &m, &n);
    printf("achkermann with recursive : %d\n", recursive_ackermann(m, n));
	printf("achkermann with loop : %d\n", loop_ackermann(m, n));
}

재귀함수를 반복문으로 구현하는 방법중 하나로 스택을 이용할 수 있다.

 

위 ackermann은 m,n값의 조건에 따라서, f(m,n)으로 표현되는데 

m != 0 && m!= 0인 경우, f(m-1,f(m,n-1))로 표현된다.

 

재귀함수를 이용할 경우, 언어 그대로 작성하기에 작성 속도는 빠르지만, 함수 호출이 많으므로 m,n값이 커지면 반복문에 비해 비효율적이다. 

 

위 ackermann은 최종적으로 m = 0일때 함수가 종료되고, 반환하는 값은 n이다. 즉, 이 함수의 리턴값은 결국 n이고, 생각해야할 변수는 m이다. 

 

함수를 합성함수라 생각하면, f(m-1,f(m,n-1))의 경우,

현재 가르키는 값은 m이 되어야 하고( f(m,n-1)값을 먼저 계산해야 하기에), 

위의 계산 후 가르켜야 할 값은 m - 1이다. ( f(m-1,*) , *은 위의 식 연산의 결과)

 

요약하면, 함수의 합성 연산이 진행될수록 연산시 사용할 m의 값이 쌓이는데

나중에 쌓인 m의 값을 먼저 연산에 사용하므로 stack을 사용한다.(반대의 경우는 큐)

 

 재귀함수를 반복문으로 표현한다는 것은

 할 일을 미뤄두는 느낌으로, 어떠한 저장공간에 연산에 필요한 값을 저장하고,

저장 방식은 함수의 합성과 같이 어떠한 연산의 패턴에 따라 바뀌는 것 같다고 생각한다.