[알고리즘] 재귀호출(자료구조4)

목차

# 재귀호출의 개념

재귀호출은 함수가 자기 자신을 호출하여 순환하여 수행되는 것으로 순환 호출 또는 Recursion이라고 부른다.
함수에서 실행해야 하는 작업에 따라 재귀호출을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성이 가능하다.

재귀호출을 사용하는 경우는?

팩토리얼 함수

대표적인 재귀호출 함수는 팩토리얼(Factiroal)인데 n에 대한 팩토리얼 함수는 1부터 n까지 모든 자연수를 곱하는 연산이다.

#include <stdio.h>

int fact(int n){
    int value;
    if(n <= 1){
        printf("\n fact(1) 호출!");
        printf("\n fact(1) 값 1 반환!");
        return 1;
    } else{
        printf("\n fact(%d) 함수 호출", n);
        value = ( n * fact(n - 1));
        printf("\n fact(%d) 값 %d 반환", n, value);
        return value;
    }
    
}
int main(int argc, char* argv[]){
    int n, result;
    
    printf("\n 정수를 입력하세요 : ");
    scanf("%d", &n);
    result = fact(n);
    printf("\n fact(%d)의 팩토리얼은 %d", n, result);
    getchar();
    return 0;
}
---------------------------
 정수를 입력하세요 : 3

 fact(3) 함수 호출
 fact(2) 함수 호출
 fact(1) 호출!
 fact(1) 값 1 반환!
 fact(2) 값 2 반환
 fact(3) 값 6 반환
 fact(3)의 팩토리얼은 6

 하노이 탑 퍼즐

#include <stdio.h>

void hanoi(int n, int start, int work, int target){
    if(n == 1){
        printf("%c에서 원반 %d를 %c로 옮긴다. \n", start, n, target);
    }else{
        hanoi(n -1, start, target, work);
        printf("%c에서 원반 %d를 %c로 옮긴다. \n", start, n, target);
        hanoi(n -1, work, start, target);
    }
}

int main(int argc, char* argv[]){
    hanoi(3, 'A', 'B', 'C');
    getchar();
    return 1;
}
----------------------
A에서 원반 1를 C로 옮긴다. 
A에서 원반 2를 B로 옮긴다. 
C에서 원반 1를 B로 옮긴다. 
A에서 원반 3를 C로 옮긴다. 
B에서 원반 1를 A로 옮긴다. 
B에서 원반 2를 C로 옮긴다. 
A에서 원반 1를 C로 옮긴다.