자료구조 ② - 자료구조 순환 ,재귀함수 -하노이탑 , 이진탐색(재귀)

 

​ 안녕하세요 소리입니다! 저번에 해봤던 재귀함수들은 모두 반복문으로 쉽게 바꿀 수 있었습니다.   하지만 이번에는 반복문으로 바꾸기 어렵거나 순환을 써야하는 경우 입니다. 함수의 호출이 맨앞에서 이루어 지는 머리순환이나 여러군데에서 자기자신을 호출 하는 경우가 대표적 입니다.       ***예제 1. 하노이탑***     규칙 1. 한번에 하나의 원판만 이동할 수 있다. 규칙 2. 맨 위에 있는 원판만 이동할 수 있다. 규칙 3. 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다. 규칙 4. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다. 하노이탑은 이 규칙들을 이용하여 봉A의 막대들을 전부 봉C로 옮기는 문제입니다.         #include <stdio.h> #include <stdlib.h> int ff(int a); //1 2 3 5 8 13 21 void g(int a); //1 2 1 3 1 2 1 --3을중심으로 대칭 //1 2 1 3 1 2 1 4 1 2 1 3 1 2 1 1213121412131215121312141413121 int main(int argc, char *argv[]) { int i; g(5); return 0; } void g(int a){ if(a==1){ printf("%d ",a); return; } else{ g(a-1); printf("%d ",a); g(a-1); } }   결과 값은 a의 값에 따라 대칭되어 나타납니다. (a=4일경우) 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1  이 숫자들은 원판이 옮겨지는 순서입니다. a=1 이 될떄 원판은 from에서 to로 옮겨지며 나머지의 경우에  from -> tmp , from->to , tmp->to  로 옮긴다.

 

***예제 2. 재귀를 이용한 이진탐색***

​

이진탐색이란?

절반으로 나눠서 가운데부터 내가 찾고싶은 값을 탐색한다.

만약 내가 찾는 값이 가운데보다 크다면? 가운데보다 큰 쪽부터 다시 반으로 나눠서 탐색!

만약 나개 찾는 값이 가운데보다 작다면? 처음부터 가운데까지 반으로 나눠서 탐색!

이렇게 반으로 나누는 동작을 반복하는 탐색입니다.

 

int binarySearch(int *arr,int find,int s,int f){ int half= (s+f)/2; if(s<=f){ if (find<arr[half]){ return binarySearch(arr,find,s,half-1); } else if(find>arr[half]) { return binarySearch(arr,find,half+1,f); } else if(find==arr[half]) { return 1; } } return 0; } <TEXTAREA/>

 

결과값을 살펴보면

이렇게 찾는값의 위치가 반환되어 나타나는 것을 알 수 있습니다.

찾는 값이 없다면 -1이 리턴되어 표시가 되겠죠?

앞의 예시들로 순환프로그래밍 기법으로 프로그램들을 작성해보았습니다.

다음번엔 배열로 찾아뵙겠습니당ㅎㅎㅎㅎ