[자료구조]재귀함수

1.

호출관계 를 중요시할것.

피보나치 수열.

 

0 1 1 2 3 5 8 13 21 34 55 . . .

 

n=1 -> 0, n=2 -> 1 :: 0번째와 1번째는 결정되어 있다.

n = otherwise -> fib(n-1)+fib(n-2) :: n번째 수는 n-1번째수 + n-2번째 수

 

[1_ex]

int Fibo(int n){

if(n==1) return 0;

else if(n==2) return 1;

else

return fib(n-1)+fib(n-2);

}

 

void main(){

int i;

for(i = 0; i<15; i++){

printf("%d", Fibo(i));

}

}

 

 

 

2.

이진탐색(Binary Search)알고리즘

 

길이가 9인 배열에 정렬된 상태로 데이터가 저장되어 있다고 가정.

*첫번째 시도

 

1

2

3

7

9

12

21

23

27

    idx0              idx1          idx2          idx3           idx4           idx5          idx6           idx7           idx8

 

1.배열 인덱스의 시작과 끝은 0과 8, (0+8)/2 = 4를 인덱스 값으로 한다.

2.idx[4]의 값이 3인지 확인한다.

-아니다.

 

*두번째 시도

 

1

2

3

7

9

12

21

23

27

    idx0              idx1          idx2          idx3           idx4           idx5          idx6           idx7           idx8

 

1.idx[4]의 값인 9와 탐색값 3을 비교한다.

2.idx[4]>3이므로 탐색범위를 인덱스 기준 0~3으로 제한, (0+3)/2 = 1.5로 나머지는 버린다.

3.idx[1]에 저장된 값이 3인지 확인한다.

-아니다.

 

*세번째 시도

1

2

3

7

9

12

21

23

27

   idx0            idx1          idx2          idx3           idx4           idx5            idx6           idx7           idx8

 

1.idx[1]의 값인 1과 탐색값 3을 비교한다.

2.idx[1]<3이므로 인덱스 기준 2~3으로 제한한다, (2+3)/2 = 2.5로 나머지는 버린다.

3.idx[2]에 저장된 값이 3인지 확인한다. 

 

if(target <idx[mid]){

last = mid-1;

else

first = mid+1;

 

 

 

3.

재귀함수

 

 

4.

이진탐색알고리즘의 재귀구현

 

이진탐색: 1.절반찍고 2.탐색대상있나확인하고 3.없으면 절반자르고 - 123 반복

 

재귀구현

0.탈출 조건이 있는지 확인.(first 와 last가 역전되면 탈출조건이다.)

1.탐색범위의 중앙에 목표 값이 저장되었는지 확인.

2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색.

 

int ar[] 탐색 주소값

int first 탐색 시작위치

int last 탐색 마지막위치

int target 탐색대상

 

 

 

012