2017년 9월 7일 목요일

Callback Function과 Iterator

재귀함수와 이터레이터는 일찍이 알았습니다만, 재귀함수를 자주 이용하지는 않았습니다.

처음으로 재귀함수를 응용했던것이 C 자료구조 수업에서 quick sort를 만들때 였으며,
그때 정말 눈 돌아갈 정도로 복잡했었기 때문에 사용을 꺼려하고 있었습니다.

재귀함수와 이터레이터는 같은 기능을 제공합니다.특정 기능을 반복하는 행위이지요.

하지만 두 기능은 상황에 따라 작업속도의 차이가 생기게 됩니다.
간단한 예를 들어 피보나치 수열 계산일때 :

반복문을 이용했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int itrway(int var)
{
    if(var<3) return 1;
    else
    {
        int cur=1,prev=1,tmp=0;
        for(int i=2;i<var;i++)
        {
            tmp=cur;
            cur+=prev;
            prev=tmp;
        }
        return cur;
    }
}
재귀함수를 이용했습니다.
1
2
3
4
5
6
7
int functionway(int var){
    
    if(var<=2) return 1;
    else return functionway(var-2)+functionway(var-1);
    
}














같은 기능을 수행하지만, 동작시간은 상이합니다.

number input : 45

1 . function call
 result :1134903170
 exec time :19.725

2 . Iterator call
 result: 1134903170
 exec time :4.724

반복문의 경우에는, 단순하게 수열을 순서대로 더했습니다. 아마..44번 계산이 전부이죠.

반면, 재귀함수의 경우에는 하나의 함수에서 2번의 함수 호출을 합니다.인자값이 1과 2가 아닌이상 또 2번 호출을 하게되고요. 불필요하게 같은 수를호출하게 될 것 입니다.

고작 45라는 숫자이기에 커다란 차이는 없지만, 숫자가 커질수록 작업 횟수와 시간은 기하급수적으로 늘어날 것 입니다.

그렇다고 재귀함수가 항상 안좋은 것은 아닙니다.
대표적인 예로, 검색 알고리즘에서는,
이터레이터 방식의 검색인 버블소트는, 굉장히 쉽게 설계가 되지만, 제가 사용했던 퀵 소트를 비교한다면, 엄청난 수준의 시간 차이가 발생했습니다.

예제를 찍어내는건 담에 하고 ㅠ

이러한 이유로, 수월하고 가벼운 프로그램을 짜기 위해서는, 우리는 최대한 경량화 작업, 그러니깐 좋은 알고리즘을 짜는 방식을 만들기 위해 반복문과 재귀함수중 어느것이 상황에 따라 더 유리한지 찾아야 할 것 입니다.


댓글 없음:

댓글 쓰기