자료구조 2강 재귀함수의 예제 소스 코드

재귀함수의 기본적인 형태의 코드

void Recursive(void)
{
  printf("Recursive call! \n");
  Recursive();
}

재귀를 매개변수만큼 실행하는 예제

코드 구현

#include <stdio.h>

void Recursive(int num)
{
  if(num <= 0)
      return;
  printf("Recursive call! %d\n", num);
  Recursive(num-1);
}

int main() {
    Recursive(3);
    return 0;
}

출력 결과

재귀함수로 구현해볼 정수 n의 팩토리얼

n! = n X (n-1) X (n-2) X (n-3) X . . . . X 2 X 1

3! = 3 X 2 X 1

5! = 5 X 4 X 3 X 2 X 1

코드 구현

#include <stdio.h>

int Factorial(int n)
{
    if(n == 0)
        return 1;
    else
        return n * Factorial(n-1);
}

int main() {
    printf("1! = %d\n", Factorial(1));
    printf("2! = %d\n", Factorial(2));
    printf("3! = %d\n", Factorial(3));
    printf("4! = %d\n", Factorial(4));
    printf("9! = %d\n", Factorial(9));
    return 0;
}

출력 결과

피보나치 수열

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ....

간단하게 정의하면 "앞의 두 수를 더해서 현재의 수를 만들어가는 수열"

수열의 n번째 값 = 수열의 n-1번째 값 + 수열의 n-2번째 값

코드 구현

#include <stdio.h>

int Fibo(int n)
{
    if(n == 1)
        return 0;
    else if(n == 2)
        return 1;
    else
        return Fibo(n-1)+Fibo(n-2);
}

int main() {
    int i;
    for(i=1; i<15; i++)
        printf("%d ", Fibo(i));
    return 0;
}

출력 결과

호출순서를 파악하기 위한 코드

#include <stdio.h>

int Fibo(int n)
{
    printf("func call param %d \n", n);

    if(n == 1)
        return 0;
    else if(n == 2)
        return 1;
    else
        return Fibo(n-1) + Fibo(n-2);
}

int main(void) {
    Fibo(7);
    return 0;
}

출력 결과

이진 탐색 알고리즘의 재귀적 구현

코드 구현

#include <stdio.h>

int BSearchRecur(int ar[], int first, int last, int target)

{

    int mid;

    if(first > last)

        return -1;          // -1의 반환은 탐색 실패 의미

    mid = (first+last) / 2;  // 탐색대상의 중앙을 찾는다.

  

    if(ar[mid] == target)

        return mid; // 탐색된 타겟의 인덱스 값 반환

    else if(target < ar[mid])

        return BSearchRecur(ar, first, mid-1, target);

    else

        return BSearchRecur(ar, mid+1, last, target);

}

int main(void) {

    int arr[]={1, 3, 5, 7, 9};

    int idx;

    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 7);

    if(idx == -1)

        printf("탐색 실패\n");

    else

        printf("타겟 저장 인덱스: %d\n", idx);

    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 4);

    if(idx == -1)

        printf("탐색 실패\n");

    else

        printf("타겟 저장 인덱스: %d\n", idx);

  

    return 0;

}

출력 결과

하노이 타워

하노이 타워는 재귀함수가 유용하게 쓰이는 대표적인 예시이다.

코드 구현

#include <stdio.h>

void HanoiTowerMove(int num, char from, char by, char to)
{
  if(num == 1)
  {
    printf("원반1을 %c에서 %c로 이동\n", from, to);
  }
  else
  {
    HanoiTowerMove(num-1, from, to, by);
    printf("원반%d을(를) %c에서 %c로 이동\n", num, from, to);
    HanoiTowerMove(num-1, by, from, to);
  }
}

int main(void) {
    HanoiTowerMove(3, 'A', 'B', 'C');
    return 0;
}

출력 결과