자료구조 예시입니다.
#include<stdio.h>
int Recursive(int num) {
if (num <= 0)
return 0; //재귀함수 종료
//return 0; 이라는 것은 함수를 종료시키겠다는 말이다.
printf("Recursive %d \n", num);
Recursive(num - 1);
}
int main() {
printf(" Hello, Recursive start \n");
Recursive(3);
return 0;
}
#include<stdio.h>
int Recursive(int num) {
if (num <= 0)
return 0; //재귀함수 종료
//return 0; 이라는 것은 함수를 종료시키겠다는 말이다.
printf("Recursive %d \n", num);
Recursive(num - 1);
}
int main() {
printf(" Hello, Recursive start \n");
Recursive(3);
return 0;
}
반복적으로 자신을 호출하는 함수를 보고 재귀함수라 부르는데,
이 예시는 가장 기본적인 구조로 Recursive라는 재귀함수를 활용하는 구조입니다.
#include<stdio.h>
int Factorial(int n) {
if (n == 0)
return 1;
else
return n * Factorial(n - 1);
}
int main() {
printf(" Hello, Recursive start \n");
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(5));
return 0;
}
두번째 예시로는 Factorial 이라는 함수를 사용하는 것입니다.
고등학교 수학시간에 배운 n!그 팩토리얼이 맞습니다!
재귀함수를 이용해 n-1을 계속해서 곱해 나가고 값이 0 이 되지 않도록 if(n==0)을 걸어주었습니다.
#include<stdio.h>
int Factorial(int n) {
if (n == 0)
return 1;
else
return n * Factorial(n - 1);
}
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\n", Fibo(i));
return 0;
}
세번째 예시로 피보나치 수열의 예시입니다.
이또한 고등학교 시간에 배운 수학문제로 피보나치 수학문제를 재귀함수를 이용해 해결한 형태입니다.
int Fibo2(int n) {
printf("func call param %d \n", n);
if (n == 1)
return 0;
else if (n == 2)
return 1;
else return
Fibo2(n - 1) + Fibo2(n - 2);
}
int main() {
Fibo2(7);
return 0;
}
네번째 예시입니다.
세번째 예시와 똑같은 패턴이지만, 출력값에서는 더 많은 라인의 값이 나온것을 알 수 있습니다.
printf를 어디에 찍느냐에 따른 차이일뿐 코드 구조는 같습니다.
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() {
int arr[] = { 1,3,5,7,9 };
int idx;
idx = BSearchRecur(arr, 0, sizeof(arr) / sizeof(int) - 1, 7);
//sizeof함수는 메모리 공간에서 소모하는 메모리의 크기를 바이트 단위로 계산해서 반환하는 연산자입니다.
printf("sizoef(arr) : %d, sizeof(int) : %d\n", sizeof(arr), sizeof(int));
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;
}
마지막 예제입니다.
BSearchRecur이라는 함수를 이용해서 이진탐색트리를 구현해봅니다.
이진탐색트리는 알고리즘에서 정말 중요한 기초가되는 중요한 부분인데요,
개인적으로 위의 코드를 달달 외워야한다고 생각합니다.
