02. 재귀(Recursion)
- 재귀함수 : 함수 내에서 자기 자신을 다시 호출하는 함수
- 재귀함수 예
- 팩토리얼(Factorial) : S002_RecursiveFactorial.c
123456789101112131415#include <stdio.h>int Factorial(int n){if (n == 0){return 1;}else{return n * Factorial(n - 1);}}int main(void){printf("9! = %d \n", Factorial(9));return 0;} - 피보나치 수열(Fibonacci Sequence) : S002_FibonacciFunc.c
1234567891011121314151617181920#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){printf("Fibo(7) = %d\n", Fibo(7));return 0;} - 이진 탐색(Binary Search) : S002_RecursiveBinarySearch.c
123456789101112131415161718192021222324252627282930313233#include <stdio.h>int BSearchRecur(int ar[], int first, int last, int target){int mid;if (first > last){return -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), 7); //7 대신 4로 수정한 후 재실행if (idx == -1){printf("탐색 실패\n");}else{printf("타겟 저장 인덱스 : %d \n", idx);}} - 하노이 탑(The Tower of Hanoi) : S002_HanoiTowerSolu.c
1234567891011121314151617#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'); //3 대신 4,5,6,7로 변경하면서 실행return 0;}
- 팩토리얼(Factorial) : S002_RecursiveFactorial.c