재귀함수와 탈출조건

자기 자신을 호출하는 함수

함수의 수식을 보면 사실, 수식 자체가 재귀적인 요소가 있다.
이게 왜 가능하냐? 가능하지 않느냐?로 따지기 보다는 함수내에서 자기자신을 호출하는 것이 가능하도록 만들었구나라고 인지를 하고, 그것의 의미를 받아들이는 편이 좋다.

#include <stdio.h>


int Fibo(int n)
{
	if (n == 1)  // 1 일때 종료, 탈출조건
		return 0;
	else if (n == 2)
		return 1;
	else
		return Fibo(n - 1) + Fibo(n - 2); 
}

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

	return 0;
}

0 1 1 2 3 5 8 13 21 34 55 89 144 233

다만 재귀 함수의 탈출조건을 명시해주는 것은 중요하므로 꼭 탈출조건은 유의하도록 하자.

호출관계와 호출 순서

호출관계는 중요하지만 호출순서는 추적해볼 수는 있지만 이해가 되지 않아도 너무 까다롭게 생각하지말고 넘어가자.

그래도 피보나치 수열은 한번 정도는 추적해보도록하자.

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


**
func call param 7
func call param 6
func call param 5
func call param 4
func call param 3
func call param 2
func call param 1
func call param 2
func call param 3
func call param 2
func call param 1
func call param 4
func call param 3
func call param 2
func call param 1
func call param 2
func call param 5
func call param 4
func call param 3
func call param 2
func call param 1
func call param 2
func call param 3
func call param 2
func call param 1

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

탐색 범위의 중앙에 원하는 값이 저장되었는지 확인하여 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작

#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); 
        // 앞부분( first, mid - 1) 재탐색
	else
		return BSearchRecur(ar, mid + 1, last, target); 
        // 뒷부분 (mid + 1, last) 재탐색
}

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("searh fails \n");
	else
		printf("target index saved : %d \n", idx);

	idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(int) - 1, 4);
	if (idx == -1)
		printf("search fails \n");
	else
		printf("target index saved : %d \n", idx);

	return 0;
}


**
target index saved : 3
search fails