[알고리즘] Recursion 이란 - 1

Recursion(재귀) 이란

void func(...){                                                                               
...
    func(...);                                                      
...
}

위의 코드와 같이 자기자신을 호출하는 함수를 Recursion,

재귀 함수라고 한다.

public class recur{
    public static void main(String [] args){                                                                
        func();
    }
 
    public static void func(){
        System.out.println("Hello world!");                        
        func();
    }
}
 

위와 같은 자바 코드를 보자.

이 함수를 우리가 main 메소드에서 호출하게되면 불행하게도

무한 루프에 빠져서 영원히 Hello world!를 호출하게 된다.

이렇게 재귀 함수는 항상 무한 루프에 빠지는것일까?

public class recur{
    public static void main(String [] args){                                                                
        int n = 4;
        func(n);
    }
 
    public static void func(int k){
        if(k<=0)
            return;
        else{
            System.out.println("Hello world!")                     
            func(k-1);
        }
    }
}
 

이 함수는 전의 함수와 약간 다르다.

main 함수에서 func를 호출하며 func 내부에서 인자 -1을 매개변수로

다시 func를 호출하게 된다.

이 경우 결과값은 어떻게 될까?

hello world는 4번 출력되게 된다.

이유는 매개 변수는 계속 1씩 감소하고 결국 0에 도달하여 return 되기 때문이다.

따라서 재귀함수가 항상 무한루프에 빠지는 것은 아니다!

재귀함수가 무한 루프에 빠지지 않게 되기 위해서는 '적절한 구조'가 필요하다

이 적절한 구조란 무엇일까?

public static void func(int k){                                                                             
    // Base Case
    if(k<=0)
        return;
    else{
        System.out.println("Hello world!")                         
        // Recursive Case
        func(k-1);
    }
}
 

바로 Base Case와 Recursive Case이다.

Base Case :  적어도 하나의 Recursion 에 빠지지 않는 경우

Recursive Case: recusion을 돌면서 Base Case에 수렴하게 하는 경우

다음의 예제를 보면서 위의 조건에 만족하는지 확인해보자

public static int fibonacci(int n){                                                            
    if(n<2)
        return n;
    else{
        return fibonacci(n-1)+ fibonacci(n-2);                                                                 
    }
}
 
 

 

첫번째 예제, 피보나치 수이다.

위의 코드는 대표적인 재귀함수의 예제인 피보나치 수를 코드화 시킨것이다.

기본식은 다음과 같다.

F(0) = 0

F(1) = 1

F(n) =  F(n-1)+F(n-2)      n > 1

n의 피보나치수 = n + n-1의 피보나치수

 

하나의 정수를 받아서 그 정수가 2보다 작으면 바로 리턴한다.

그렇지 않으면 fibo 함수에 각각 n-1, n-2를 넣은 함수의 값을 더해 리턴한다

public static int factorial(int n){                                                            
    if(n==0)
        return 1;
    else{
        return n*factorial(n-1);                                                                            
    }
}
 
 

두번째 예제, 팩토리얼 이다.

팩토리얼의 기본식은 다음과 같다.

0! = 1

n! = n x (n-1)!      n > 0

따라서, 이 기본식을 코드화 시키면 위의 코드로 변환이 가능하다

우선 인수가 0이면 1을 리턴한다

그렇지 않으면 인자값과 인자 - 1을 매개변수로 전달하는 함수의 결과값을 더하여

리턴한다.

public static double power(double x, int n){                                                                 
    if(n==0)
        return 1;
    else{
        return x*power(x, n-1);                                      
    }
}

세번째 예제, 제곱이다

x^0 = x

x^n = (x^n-1)*(x)    x > 0 

이 예제도 마찬가지로 기본식을 코드화 시키면 위의 코드로 변환이 가능하다

인자값이 0이면 1을 리턴해주고

그렇지 않으면 n이 0이될때까지 x값을 계속해서 곱해준다.

public static double gcd(int m, int n){                                                                      
    if(m<n){
        int tmp=m; m=n; n=tmp;                                     
    }
    if(m%n==0)
        return n;
    else{
        return gcd(n, m%n);
    }
}

마지막 예제, 최대 공약수이다.

m>=n인 두양의 정수 m 과 n에 대해서 m이 n의 배수이면 gcd(m,n) = n이고,

 그렇지 않으면 gcd(m,n) = gcd(n,m%n)이다

증명에 대해 찾아보고 싶다면 유클리드 호제법 또는 Euclid Method를 검색하면 된다

public static int gcd(int p, int q){                                                                         
    if(q==0)
        return p;
    else
        return gcd(q,p%q);                                          
}

참고)

다음은 좀더 단순한 버전의 유클리드 호제법이다.

출처: 부경대 권오흠 교수님, 영리한 프로그램을 위한 알고리즘 강좌