Recursion(순환)-1

Recursion vs Iteration

 

• 모든 순환함수는 반복문으로 변경 가능하다.
• 모든 반복문은 recursion으로 표현 가능하다.
• 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다
• 함수 호출에 따른 오버헤드가 존재한다.(매개변수 전달, 액티베이션 프레임 생성 등)

 

자기 자신을 호출하는 함수(메서드)를 Recursion이라고 한다.

 

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

Recursion은 위와 같은 코드를 보면 메서드안에 자기 자신을 다시 호출함으로 무한루프에 빠질 수 있다.

 

 

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

Hello...
Hello...
Hello...
Hello...
 
 
 
 

 

무한루프에 빠지지 않으려면 2가지 조건을 만족해야 한다.

 

1. Base case : 적어도 하나의 자기자신을 호출하지 않고 recursion에 빠지지 않는 경우가 존재해야 한다.

2.  Recursive case : recursion을 반복하다 보면 결국 base case로 수렴해야 한다.

 

 

public class Code 03{
    public static void main(String [] args){
        int result = func(4);
        System.out.print(result);
    }
 
    public static int func(int n){
 
        if(n==0){
            return 0; // n= 0 이면 총 합은 0 이될수 밖에 없다
       }else{
            return n + func(n-1);
    }
}

public class Code 03{
    public static void main(String [] args){
        int result = func(4);
        System.out.print(result);
    }
 
    public static int factorial(int n){
 
        if(n<=0)
            return 1;
        else{
            return n * factorial(n-1);
    }
}

 

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

ex_3 : 피보나치 수열 구하는 메서드

 

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);
}