Algorithm - Recursion(순환)

1. What is Recursion? 

Recursion은 자기 자신을 호출하는 메서드를 의미하며, Recursion을 번역하면 "순환, 재귀 메서드" 라 한다.

 

Java를 통해 Recursion을 구현해보자. methodForTest 메서드를 main 메서드에서 호출했으며, methodForTest 메서드내에서 다시 한번 자기 자신을 호출하였다. 아래 코드와 같이 실행하면 어떤 결과가 발생하는가?

public class Test {
    public static void main(String[] args) {
        methodForTest();
    }
    
    private static void methodForTest() {
        System.out.println("Say Hello!");
        methodForTest();
    }
}

당연하게도 무한 루프가 발생하여 "Say Hello!"를 무한히 출력하는 일이  발생한다.

 

그럼, Recursion이 무한 루프에 빠지지 않도록 설계할 수 없는가? 아래와 같이 구현하면 N번 실행시킬 수 있다. 

public class Test {
    public static void main(String[] args) {
        methodForTest(4);
    }
	
    private static void methodForTest(int count) {
        if(count<=0) 
            return;
        else { 
            System.out.println("Hello!");
            methodForTest(count-1);
        }
    }
}

count = 0가 되면 차례대로 methodForTest(1) ~ methodForTest(4) 까지 차례대로 Return하여 종료시키며, 최종적으로 처음 호출했던 main 메서드로 돌아가게 된다.

 

∴ Recursion은 적절한 구조를 갖는다면 infinite loop에 빠지지 않고, finite loop내에서 동작할 수 있다.

 

 

2. What is proper structure for recursion?

Q) Recursion을 위한 적절한 구조는 구체적으로 어떤 것을 의미하는가?

A) finite loop에서 recursion을 동작하기 위해서는 아래와 같이 크게 두 가지 성절을 가져야 한다.

 

Proper structure for recusion

• Base case : Recursion loop에서 빠져 나올 수 있는 코드
• Recursion case : 계속해서 자기 자신을 호출하는 reursion 코드 
  (단, base case로 수렴해야만한다. 만약 base case에 수렴하지 않는다면 k 값이 0으로 가까워지지 않고, k 값이 점차 증가하여 무한 루프(Infinite loop)에 빠질 수 있기 때문에 반드시 base case로 수렴해야 한다.)

 

 

3. Example of recursion

3.1. 1 ~ n까지 더하기

public class Test {
    public static void main(String[] args) {
        int sum = func(4);
        System.out.printf("Result of sum: %d\n", sum);
    }
	
    private static int func(int n) {
        if(n==0)
            return 0;
        else 
            return n + func(n-1);
    }
}

• n = 0이 될 때까지 func 메서드를 이용하여 recusion을 한다.
• n = 0이 되면 0을 return하는 것을 시작으로 차례차례 return하여 최종적으로 main 메서드에 4 + 3 + 2 + 1 + 0 = 10을 반환하게 된다. 

 

3.2. factorial 

public class Test {
    public static void main(String[] args) {
        int result = factorial(4);
        System.out.printf("Result of factorial: %d.\n", result);
    }
	
    private static int factorial(int n) {
        if(n==0)
            return 1;
        else 
            return n * factorial(n-1);
    }
}

• n = 0이 될 때까지 factorial 메서드를 recursion을 한다.
• n = 0이 되면 1을 return 하는 것을 시작으로 차례차례 return하여 최종적으로 main 메서드에 1 * 1 * 2 * 3 * 4 = 24를 반환하게 된다.

 

3.3. x^n 계산

public class Test {
    public static void main(String[] args) {
        int result = calculator(2, 5);
        System.out.printf("Result of calculation: %d.\n", result);
    }
	
    private static int calculator(int value, int expo) {
        if(expo == 0)
            return 1;
        else 
            return value * calculator(value, expo-1);
    }
}

 

3.4. Fibonacci number

public class Test{
    public static void main(String[] args) {
        int value = fibonacci(5);
        System.out.printf("Value: %d.\n", value);
    }
	
    private static int fibonacci(int index) {
        if(index<2)
            return index;
        else
            return fibonacci(index-1) + fibonacci(index-2);
    }
}

 

3.5. find GCD by using Euclid method

Euclid method

public class Test {
    public static void main(String[] args) {
        int GCD = findGreatestCommonFactor(20, 30);
        System.out.printf("%d's greatest common factor: %d\n", 20, GCD);
    }
	
    private static int findGreatestCommonFactor(int m, int n) {
        if(m<n) {
            int tmp=n; n=m; m=tmp; //*** swap m and n.
        }
		
        if(m%n==0)
            return n;
        else 
            return findGreatestCommonFactor(n, m%n);
    }
}