재귀 함수

재귀 함수가 어려운 이유?

호출 관계는 파악하기 쉬우나, 호출 순서를 파악 하기가 힘들어진다.

하지만 호출 순서는 재귀가 복잡해 질수록 파악 하기가 힘들어지고,

호출 순서를 파악해야 될 상황이 오기전에 호출 관계를 파악하여 해결하여야한다.

그리고 재귀 함수는 자칫 잘못 이용하면 시간이 오래 걸리게 되고 프로그램에 부담이 되기에 조심하여야 한다.

재귀 함수의 진행 및 탈출 예

void Recursive(int num)
{
 if(num <= 0)
 {
  return;
 }
 
 printf("Recursive call : %d\n",num);
 
 Recursive(num-1);
}
 
int main()
{
 Recursive(3);
 
 return 0;
}

재귀함수를 이용한 팩토리얼 예

#include <stdio.h>
 
int total;
 
int factorial(int n)
{
  if(n == 0) return 1;  
 
  else return n*factorial(n-1);
}
 
 
int main()
{
 int n;
 scanf("%d",&n);
 
 total = factorial(n);
 
 printf("%d",total);
 
 return 0;
}

이진 탐색 알고리즘을 재귀적으로 표현한 예

int BSearchRecur(int ar[], int first, int last, int target)
{
 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); // 뒷부분을 대상으로 재 탐색
 }
 
}