재귀(Recursion)

재귀함수 : 어떠한 함수가 있을 때 자기 자신을 호출하는 함수

 

ex1) 팩토리얼

#include <stdio.h>

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

int main(void)
{
	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;
}

 

ex2) 피보나치 수열

#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;
}

ex3) 이진 탐색

#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, 2);
	if (idx == -1)
		printf("탐색 실패 \n");
	else
		printf("타겟 저장 인덱스: %d \n", idx);

	return 0;
}

재귀는 성능이 떨어져. 재귀에 익숙해지기 위해

 

ex4) 하노이 타워

#include <stdio.h>

void HanoiTowerMove(int num, char from, char by, char to)
{
	if (num == 1)    // 이동할 원반의 수가 1개라면
	{
		printf("원반1을 %c에서 %c로 이동 \n", from, to);
	}
	else
	{
		HanoiTowerMove(num - 1, from, to, by);    // 3단계 중 1단계
		printf("원반%d을(를) %c에서 %c로 이동 \n", num, from, to);  // 3단계 중 2단계
		HanoiTowerMove(num - 1, by, from, to);    // 3단계 중 3단계
	}
}


int main(void)
{
	// 막대A의 원반 3개를 막대B를 경유하여 막대C로 옮기기
	HanoiTowerMove(3, 'A', 'B', 'C');
	return 0;
}