09. 재귀 함수 문제풀이

이전 글에서 안내하였던 재귀함수 공부를 위한 다양한 문제들을 풀어보도록 한다.

 

1. 팩토리얼 계산

#include <stdio.h>

int factorial(int n){
    if(n <= 1) return 1;
    return n * factorial(n-1);
}

int main()
{
    int n;
    
    printf("n값을 입력해주세요 : ");
    scanf("%d", &n);
    
    printf("%d! = %d", n, factorial(n));
    
    return 0;
}

 

2. n번째 피보나치수열 값 계산

#include <stdio.h>

int fibo(int n){
    if(n <= 1) return n;
    return fibo(n-1) + fibo(n-2);
}

int main()
{
    int n;
    
    printf("n값을 입력해주세요 : ");
    scanf("%d", &n);
    
    printf("%d번째 피보나치 값은 %d", n, fibo(n));
    
    return 0;
}

 

3. 하노이 타워

#include <stdio.h>

void hanoi(int n, char from, char to, char temp) {
    if (n == 1) {
        printf("%c에서 %c로 원판 1을 이동\n", from, to);
        return;
    }
    hanoi(n-1, from, temp, to);
    printf("%c에서 %c로 원판 %d을 이동\n", from, to, n);
    hanoi(n-1, temp, to, from);
}

int main() {
    int n = 3; // 원판의 개수
    hanoi(n, 'A', 'C', 'B'); // 'A', 'B', 'C'는 각각 기둥의 이름을 나타냄
    return 0;
}

 

4. 이진 탐색

#include <stdio.h>

int binarySearch(int arr[], int left, int right, int x) {
    if (left <= right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] == x) 
            return mid;
        else if (arr[mid] > x) 
            return binarySearch(arr, left, mid-1, x);
        else 
            return binarySearch(arr, mid+1, right, x);
    }
    
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int x, n = sizeof(arr) / sizeof(arr[0]);
    
    printf("찾을 값을 입력해주세요 : ");
    scanf("%d", &x);
    
    int index = binarySearch(arr, 0, n-1, x);
    if (index == -1)
        printf("%d는 배열에 존재하지 않습니다.", x);
    else 
        printf("%d는 배열의 %d번째 인덱스에 존재합니다.", x, index);
        
    return 0;
}