Data Structures & Algorithms

[Data Structures] 재귀 (Recursion)의 이해

숄구-ml 2022. 5. 4. 20:47

재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 무기이다 

 

 

1. 재귀함수의 흐름 

출처: https://velog.io/@mmindoong/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9E%AC%EA%B7%80Recursion

 

  • Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면, Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 된다
  • Recursive 함수를 정의하는데 있어서 '탈출조건'을 구성하는 것은 매우 중요한 일이다 

 

 

2. 재귀의 활용 - 피보나치 수열

  • 피보나치 수열은 재귀적인 형태를 띠는 대표적인 수열
  • 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ....
  • 수식 표현

출처: https://jwlee010523.tistory.com/entry/%EC%9E%AC%EA%B7%80%EC%9D%98-%ED%99%9C%EC%9A%A9

  • 코드 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
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(void)
{
    int i;
    for(i=1; i<15; i++)
        printf("%d ", Fibo(i));
    
    return 0;
}
    
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 cs

 

 

 

 

3. 재귀의 활용 - 이진 탐색 알고리즘의 구현

  • 이진 탐색 알고리즘의 반복 패턴 - 1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인 2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작
  • 이진 탐색 알고리즘의 탈출 조건 - 탐색 범위의 시작위치 first가 탐색 범위의 끝 위치 last 보다 커지는 경우
  • 코드 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
int BSearchRecur(int ar[], int first, int last, int target)
{
    int mid;
    if (first > last)
        return -1;
    mid = (first+last) / 2;
    
    if (ar[mid] == target)
        return mid;
    else if (ar[mid] < target)
        return BSearchRecur(ar, first, mid-1, target);
    else
        return BSearchRecur(ar, mid+1, last, target);
        
}
 
int main(void)
{
    int arr[] = {1,3,5,7,9}
    int idx;
 
    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 7);
    if(idx == -1)
        printf("failed to search \n");
    else
        printf("target index: %d \n", idx);
 
    idx = BSearchRecur(arr, 0, sizeof(arr)/sizeof(int)-1, 4);
    if(idx == -1)
        printf("failed to search \n");
    else
        printf("target index: %d \n", idx);
 
    return 0;
}
    
 cs

 

728x90