재귀함수

1. 재귀함수란?

- 함수 내에서 자기 자신을 다시 호출하는 함수

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

 

2. 관련 문제

1. 피보나치 수열

#include <stdio.h>

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

int main() {
	int n;
	scanf("%d", &n);
	printf("%d\n", fibo(n));

	return 0;
}

 

2. 이진탐색

#include <stdio.h>

int BinarySearch(int* arr, int left, int right, int n) {
	if (left > right)
		return 0;

	int mid = (left + right) / 2;

	if (arr[mid] == n)
		return 1;
	else if (arr[mid] < n)
		return BinarySearch(arr, mid + 1, right, n);
	else
		return BinarySearch(arr, left, mid - 1, n);
}

int main() {
	int arr[] = { 1, 3, 4, 6, 9 };
	if (BinarySearch(arr, 0, sizeof(arr) / sizeof(int) - 1, 1)) {//(배열, 시작index, 끝index, 찾는 값)
		printf("find");
	}
	else {
		printf("not exist");
	}

	return 0;
}

 

3. 하노이탑

#include <stdio.h>

void hanoi(int n, char start, char mid, char end) {
	if (n == 1)
		printf("%c에서 %c로 이동\n", start, end);
	else {
		hanoi(n - 1, start, end, mid);
		printf("%c에서 %c로 이동\n", start, end);
		hanoi(n - 1, mid, start, end);
	}
}

int main() {
	hanoi(3, 'A', 'B', 'C'); //A에서 B를 이용해 C로 옮기자
	return 0;
}