Data Structure Chapter 2 - recursion.md

Data Structure Chapter 2 - recursion

• 2-14, 재귀호출을 이용해 팩토리얼 값 구하기

#include <stdio.h>

long int fact(int);

int main() {

    int n;
    long int res;
    printf("정수 입력? ");
    scanf("%d", &n);
    res = fact(n);
    printf("\n =>fact(%d) is %ld!\n",n,res);

    return 0;
}

long int fact(int n) {
    long int val;
    if (n<0) {
        return 0;
    }
    else if (n<=1) {
        return 1;
    }
    else {
        printf("fact(%d) called!\n",n);
        val = (n*fact(n-1));
        printf("fact(%d) returned %ld!\n", n, val);
        return val;
    }
}

$ gcc 2-14.c -o 2-14.out && ./2-14.out
정수 입력? 4
fact(4) called!
fact(3) called!
fact(2) called!
fact(2) returned 2!
fact(3) returned 6!
fact(4) returned 24!

 =>fact(4) is 24!

• 복잡한 재귀 구조 문제는 재귀호출을 사용해야: 예> 하노이탑 퍼즐
• 2-15, 재귀호출을 이용해 하노이탑 풀기

#include <stdio.h>

long int hanoi(int n, int start, int work, int target);

int main() {

    long int tt = 0;
    tt = hanoi(3, 'A', 'B', 'C');
    printf("total: %ld", tt);

    return 0;
}

long int hanoi(int n, int start, int work, int target) {
    long int nums = 0;
    printf("line 16!\n");
    if (n==1) {
        printf("%c에서 원반 %d를 %c로 옮김.\n", start, n, target);
        printf("line 18!\n");
        nums += 1;
    }
    else {
        /* 원반 중 가장 큰 크기인 것을 제외한 경우 */
        nums += hanoi(n-1, start, target, work);
        printf("%c에서 원반 %d를 %c로 옮김.\n", start, n, target);
        printf("line 24!\n");
        /* 원반 중 가장 큰 크기인 것을 목표한 자리에 놓고 나머지를 옮김 */ 
        nums += hanoi(n-1, work, start, target);
    }
    return nums;
}

$ gcc 2-15.c -o 2-15.out && ./2-15.out 
line 16!
line 16!
line 16!
A에서 원반 1를 C로 옮김.
line 18!
A에서 원반 2를 B로 옮김.
line 24!
line 16!
C에서 원반 1를 B로 옮김.
line 18!
A에서 원반 3를 C로 옮김.
line 24!
line 16!
line 16!
B에서 원반 1를 A로 옮김.
line 18!
B에서 원반 2를 C로 옮김.
line 24!
line 16!
A에서 원반 1를 C로 옮김.
line 18!
total: 4