[자료구조] 자료구조의 기초 - 재귀함수 완벽이해

[목차]

 

재귀함수란 무엇일까?

자료구조에서 꼭 필요한 개념 중 하나인 재귀함수입니다.

 

이 재귀함수를 이해하지 못한다면 앞으로 배울 자료구조를 이해 할 수 없을만큼 가장 중요한 파트 중 하나입니다.

 

일단 이 재귀함수를 알아보기전에 순환과 반복을 알아보도록 합시다.

 

 

[ 순환과 반복]

 

코드에서 값들을 반복하기 위한 방법으론 순환과 반복 이 두가지 개념이 존재합니다.

 

순환호출은 함수 안에 함수로 들어가는 것 즉 재귀함수를 일컫는 말입니다.

 

예를들어 

 

int fact(int n){

    if( n<= 1) return 1;
    else return n * fact(n-1);
}

 

이런식으로 fact 메서드 안에서 메서드를 호출 하는 방법을 순환방법이라고 합니다.

 

반복은 저희가 잘 알고있는 단순 반복 즉 for문의 형태를 반복이라고 합니다.

 

그렇다면 이 순환과 반복을 사용할 때 어떠한 경우에 사용 할 것인가?

 

대표적으로 팩토리얼 , 거듭제곱, 피보나치의 수열 등이 있습니다.

 

무작정 순환 호출이 좋은 것이 아니라 상황에 따라 써야 합니다.

 

그렇다면 이 순환호출은 재귀함수라 했습니다.

 

이 재귀함수는 어떤식으로 사용하는지 알아봅시다.

 

 

 

[팩토리얼]

 

팩토리얼의 경우 5!라고 한다면 

 

5 * 4 * 3 * 2 * 1 = 120이 나오는것이 팩토리얼 입니다.

 

그렇다면 이 과정을 재귀함수로 구현해봅시다.

 

int fact(int n);
int main(void) {

    int n = fact(5);
    printf("%d",n);
}

int fact(int n){

    if( n<= 1) return 1;
    else return n * fact(n-1);
}

 

 

간단한 코드입니다.

 

fact(5)를 넣으면 5 * 4* 3* 2 * 1 = 120이 되는 과정입니다.

 

우리가 알아야 할 것은 재귀함수입니다.

 

 

 

이 부분을 본다면 fact 메서드 안에서 fact 메서드를 또 호출하였습니다.

 

이런 경우에는 스택이라는 곳에 함수가 쌓이게 됩니다.

 

자 한번 봅시다. 저희는 5를 넣었습니다.

 

 

 

 

그렇다면 스택에는 이런식으로 함수들이 쌓이게 됩니다.

 

자 이 과정을 천천히 알아보도록 합시다.

 

저희는 fact(5)에 값을 넣었습니다.

그렇다면 첫번째 fact 함수가 호출 될 것 입니다.

그렇게 된다면 n = 5가 됨으로

 

5 * fact( 5 - 1) 이 리턴됨으로

5 * fact( 4) 가 스택에 저장될 것 입니다.

 

그 후 다시 두번째 fact 메서드가 호출되고

n = 4가 됩니다.

그렇게 되면 4 * fact( 4 - 1)임으로

 

4 * fact (3) 이 스택에 저장됩니다.

 

이 형식으로 쭉 저장되다가 

 

n = 1이 되는 fact 메서드가 있을 것 입니다.

그 fact 메서드는 리턴값이 1이 되기때문에 스택에 상수 1이 저장됩니다. 

 

 

 

 

 

 

이렇게 n이 들어가게 됩니다.

 

 

 

 

첫번째 fact 메서드입니다.

 

n = 5임으로 n * fact ( n - 1) 리턴값입니다. 그렇다면 스택 메서드에는

 

n * fact (4)가 저장되고 스택에 저장

 

 

 

그 후 다시 fact 메서드 호출.

 

그렇다면 n =  4가 됩니다.

그러면 4 - fact(3)임으로 스택에 저장.

 

 

 

스택은 저런형식으로 저장될 것 입니다.

 

여기서 중요합니다.

혹시 기억나십니까?

 

 

 

n <= 1보다 작거나 같으면 return1을 하라고 했습니다.

 

즉 맨위에 있는 함수는 리턴 값이 1이 됩니다.

 

즉 return 1을 반환했음으로 더이상의 재귀 호출이 없습니다.

 

왜냐하면 자기 자신을 더 이상 호출하지 않으니까요. 

 

그렇기 때문에 스택에 있는 함수는 하나하나 빠지게 될 것 입니다.

 

 

 

즉 이러한 형태가 됩니다.

1 * fact (0)은 return 1을 가집니다.

 

그 후 여기서 중요합니다!!

 

자 여기서 살짝 어려운데

 

잘보면 1 * fact ( 0 )이라고 했습니다.

 

1은 함수가 아니죠? fact(0)의 리턴값은 무엇입니까?

바로 return 1 입니다.

 

그러니까 fact (0)의 반환 값은 1입니다.

 

그러면 1 * 1이 되는 겁니다. 

 

이해가 되십니까?

 

마지막 스택에 함수인 1 * fact ( 0)을 다시봅시다.

 

 

여기서 return 1이라고 했음으로

 

1은 그대로 계산된 상태에서 fact(0)의 값만 1이 되는겁니다.

 

만약에 마지막 함수가 1000 * fact ( 0)이라고 하면 

 

리턴값이 1이 아니라

 

1000이 되는겁니다. 즉 fact(0)이 함수니까 이 함수의 리턴 값은 1이니까

이 함수의 리턴값만 1이되는 겁니다.

 

그렇게 되면 1 * 1 = 1임으로 스택에 상수 1저장

그러면 더이상 재귀 호출이 없음으로 스택에 값이 빠집니다.

 

1 * fact(0)은  = 1

이 리턴된 값이 다시 스택밑에 있는 함수에 들어갑니다.

 

그 밑에 있는 함수는

 

2 * fact ( n - 1)이였죠?

 

여기서 또 잘 생각해야 합니다.

 

저희는 함수를 재귀를 돌리고 있습니다.

 

맨 스택에 쌓인 값은 1이니까 1의 값이 2 * fact ( n -1 ) fact함수부분에 들어갑니다.

 

즉 2 * fact ( 1 - 1)이 되는게 아니라 2 * fact(1) 그대로 들어갑니다.

즉 리턴된 값이 다음 함수에 그대로 들어가서 계산이 되는 겁니다.

 

 

이것이 재귀함수 입니다.

 

다들 재귀함수라고 하면 햇갈려 하는 경우가 많습니다.

일단 팩토리얼의 경우 너무 쉬운 재귀함수니 아직까지 이해가 되지 않을 수 있습니다.

여러 예제가 있으니 하나하나 따라오면서 이해하시면 됩니다.

 

 

그렇다면 또 다른 예제를 한번 보도록 하죠.

 

 

[거듭 제곱]

 

int power(int value , int pow){
    if(pow==0) return 1;
    else if(pow%2==0) {
        return power(value * value,pow/2);
    } else{
        return value * power(value * value, (pow-1)/2);
    }

}

 

이 코드는 거듭 제곱을 구하는 코드입니다.

 

만약에 power(6,3)을 넣는다면 6 * 6 * 6 = 216이 나와야 하죠.

 

아까와 같은 팩토리얼 방식으로 동작합니다.

 

즉 이런식이 되겠지요.

 

자 한번 봅시다.

 

처음에 power ( 6 , 3 )을 넣었기 때문에 

 

첫번째 스택에는 6 * (36 , 1)이 저장됩니다.

 

두번째 스택에서는 n = 36이기 때문에 

 

36 * (1296 , 0)이 두번째 스택에 저장됩니다.

 

 

 

이 36 * pow ( 1296 , 0)의 리턴값은 1입니다.

 

자 위에서 설명드렸습니다.

 

36 * pow ( 1296  , 0)인 경우 

 

power(1296 , 0) 이 함수의 리턴값은? 1입니다.

 

그렇게 되면 36 * 1이 되는겁니다.

 

왜?

 

저희는 함수를 재귀로 돌리고 있기 때문에 36은 함수가 아니라 "상수"입니다.

그렇기 때문에 36 * 1이 되는 것 입니다.

 

즉 pow의 함수의 리턴 값은 1임으로

 

36 * 1 = 36이 들어갑니다.

 

 

즉 이런 형태로 재귀가 돌아가는 것 입니다.

 

저희는 재귀를 "함수"로 돌리기 때문에 재귀  "함수"인 것입니다.

 

 

이제 다음 스택은 다들 아실꺼라 생각합니다.

리턴된 값이 36임으로 다음 함수에 36이 "그대로" 들어갑니다.

함수니까 리턴된 값 그대로 들어가는 겁니다.

 

그렇다면 36 * 6 = 216임으로 정답은 216이 되겠죠.

 

자 그렇다면 이제 슬슬 감이 잡히실겁니다.

 

이제 이 마지막문제로 완벽 이해를 하도록 합시다.

 

 

public static int recursive(int n){

    if(n < 1) return 2;
    else {
      return  (2 * recursive(n-1)+1);
    }
}

 

 

 

자 이문제 역시 위에 문제와 똑같습니다.

 

자 이 인자값에 5를 넣었다고 가정해봅시다.

 

 

자 한번 봅시다.

 

return ( 2 * f ( n - 1 ) + 1 )이라고 했음으로 무조건 함수부분 부터 들어가게 됩니다.

 

그렇게 되면 저기 글처럼 저런식으로 계속해서 들어가게 되겠죠.

 

그리고 마지막 함수부분을 봅시다.

 

 

2 * f ( 0 ) + 1인 경우 봅시다.

 

위에 코드에 함수의 n = 0 을 가질때 return 2를 하라고 했습니다.

 

 

즉  2 * f ( 0 ) + 1이면 함수 "만 " 리턴 2를 가지게 됩니다.

 

그렇게 되면 계산식은 2 * 2 + 1이 되겠죠.

 

 

그러면 값 5는 다시 f ( 1 )로 넘어갑니다.

 

그러면 2 * ( 5 ) + 1이 됩니다. f ( 0 )의 리턴 값은 5이기 때문에

 

 

f (1)은 5를 받게 됨으로 2 * ( 5 )  + 1 = 11을 받게 됩니다.

 

그 후 다시 함수로 내려갑니다.

 

 

2 * f ( 2 ) + 1이면 이 f ( 2 )의 함수는 11을 받게되겠죠.

 

f ( 1)의 함수의 리턴 값이 11이기 때문에

 

 

그렇게 되면 다시 계산식은 2 * 11 + 1이 됨으로  = 23이 됩니다.

 

그렇게 쭉 내려가다보면 답은 95가 됩니다.

 

그렇다면 재귀함수를 여러개 쓰면 어떤식으로 일어날것인가?

 

피보나치 수열의 경우를 한번 보도록 하죠.

 

[피보나치의 수열]

 

피보나치의 수열은 앞의 두 개의 숫자를 더해서 뒤의 숫자를 만든다.

즉

0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 89 , 144

이런식으로 앞의 두개의 숫자를 더해서 뒤에 숫자를 만드는 방식을 말합니다.

 

public class Main {

    public static void main(String[] args) {
        int fib = fib(6);
        System.out.println(fib);
    }
    public static int fib(int n){

        if(n == 1) return 1;
        if(n == 0) return 0;
        else return fib(n-1) + fib(n-2);
    }
}

 

코드로 본다면 이렇게 됩니다.

 

여기에서 볼 것은 저희는 이때까지 재귀함수를 한번 썻던 것으로 기억합니다.

 

하지만 여기에서 보면 리턴 값에 재귀 함수가 두개가 들어가 있습니다.

 

이 경우에는 재귀 함수를 한번 쓴 것과 완전히 달라지고

 

 

이런식으로 이진트리로 계속해서 나아갑니다.

언제까지? n의 값이 0이거나 1일때까지 계속해서 이진트리 형식으로 뻗어 나갑니다.

리턴 값의 재귀함수가 두 개가 들어간다면 무조건 이진 트리 형식으로 진행됩니다.

 

그렇다면 리턴 값이 두개로 들어간 재귀 함수 한개를 더 보도록 합시다.

 

17. 이항계수를 계산하는 순환함수를 작성하시오. 또한 반복함수로도 작성하시오.

 

이항계수란?

 

이항 계수는 조합론에서 사용되는 개념으로 , 주어진 집에서 원하는 개수만큼 원소를 선택 하는

방법의 수를 나타낸다.

다시말해 n개의 원소 중에서 k개의 원소를 선택하는 경우의 수를 의미한다.

 

예를들어 5개의 원소 (A,B,C,D,E) 중에서 2개의 원소를 선택하는 경우

C(5,2)로 표기하며 다음과 같이 계산된다.

 

C(5,2) = 5! / (2! * 3!) = 10

 

!는 팩토리얼을 나타내며 , 5! = 120을 의미한다.

 

즉 5개의 원소중 2개의 원소를 선택할때의 경우의 수는 10개가 됨으로

 

이항계수 (5,2)의 경우의 수는 10이된다.

 

마찬가지로 C(8,2)을 할경우

 

8! / 5! * 2! 이됨으로 

 

40,320/(2*720) = 28

경우의 수는 28개가 된다.

 

이렇게 이항함수를 계산하는 코드도 마찬가지로 두 개의 재귀 함수가 들어갑니다.

 

int binomial(int n,int y){

    if(n == y || y == 0) return 1;

    return binomial(n - 1 , y - 1) + binomial(n - 1 ,y);

}

 

코드는 이렇습니다.

피보나치 수열 형식과 같은 리턴 값의 두개의 재귀함수가 들어갔습니다.

 

이런 경우 리턴 값이 재귀 함수가 둘이라면 반드시 이진 트리 형식이 일어납니다.

 

 

이런식으로 이진트리 형식으로 뻗어나가며 답은 10이됩니다.

 

재귀 함수 3개를 쓰는 경우는 거의 없음으로 두 개의 재귀함수가 어떤식으로 동작하는지만 알면 됩니다.

 

이렇게 재귀함수 부분은 제대로 이해한다면 어렵지 않은 내용입니다.

 

저의 경우는 재귀함수를 이해하는데 꽤 오래걸렸는데 

이렇게 하나하나 깊이 파고든다면 이해하는데는 문제가 없을꺼라 생각합니다.