재귀2

재귀함수를 활용한 시간이었다. 재귀의 개념을 전에 나왔던 이진 탐색알고리즘에 활용해서 직접 코딩 해 볼 수있었다.

재귀함수는 말그대로 재귀적 상황에서 쓰면 좋을 것 같다. 즉 귀납적으로 해결할 수있는 문제가 발생햇을때 사용할만한 방식이라고 생각된다.

 

이진 탐색 알고리즘을 재귀적으로 구현해 보았다. 책에는 이미 예제가 있었지만 내 방식대로 코딩을 했다 역시 프로그램엔 뭔가 입력하는게 있어야 만드는 맛이 있다.

#include <stdio.h>

int binarysearchalgol(int arr[], int first, int last, int target)
{
 int mid;
 if (first > last)
  return -1;
 mid = (first + last) / 2;

 if (arr[mid] == target)
  return mid;
 else if (arr[mid] < target)
  return binarysearchalgol(arr, mid + 1, last, target);
 else
  return binarysearchalgol(arr, first, mid - 1, target);
}

int main()
{
 int arr[5] = { 1,3,5,7,9 };
 int idx=0;
 int target;

 while (idx != -1)
 {
  printf("What do you want to find?\n");
  scanf_s("%d", &target);

  idx = binarysearchalgol(arr, 0, sizeof(arr) / sizeof(int) - 1, target);

  if (idx == -1)
   printf("none\n");
  else
   printf("I find target in arr[%d]\n", idx);

 }
 return 0;
}

 

반복을 무한히 시킬까 생각도 해봤는데 그래도 없을때 꺼지는게 나을 것같아서 그렇게 했다.

scanf_s같은 경우는 예전엔 그냥 scanf만 써도 됐는데 요즘 컴파일러에선 저런방식으로 써줘야 워닝이 안뜨는 것 같다.

 

다음번엔 하노이타워에 대해 하는데 이건 그냥 재귀함수를 더 이해하기 위한 수단으로 쓰는것같다 나름 재밌으니 읽어 보겠다.