6. Recursion (Java)

1. Recursion (순환, 재귀함수)

 - 자기 자신을 호출하는 메서드

void func(){
  func();
}

1) 예제 1

 - Hello...가 무한으로 출력된다. (무한 루프에 빠짐)

public class code01 {
  public static void main(String [] args) {
    func();
  }


  public static void func() {
    System.out.println("Hello...");
    func();
  }

}

 

2) 예제 2

 - recursion은 항상 무한루프에 빠지지 않음.

 - Hello...가 4번만 출력 됨.

 - Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.

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

 - base case와 recursive case, 두 가지의 조건이 성립하면 recursion이 무한루프에 빠지지 않는다.

 

package inflearn.chapter2.recurtion;

public class RecursionEx02 {
	public static void main(String[] args) {
		int n = 4;
		func(n);
	}
	
	public static void func(int k) {
		if (k <= 0) //base case
		  return;
		else {
		  System.out.println("Hello...");
		  func(k-1); //recursive case
          
           //func(K+1); causing infinite loof. 
		}
	}
	
}

 

3) 예제 3

 - 0부터 n-1까지의 합을 구한 후 n을 더하는 recursion

 - 즉, 0~ n까지의 합을 구함.

package inflearn.chapter2.recurtion;

public class RecursionEx3 {
  public static void main(String[] args) {
    int result = func(4);
    System.out.println(result);
  }	
  // n(n+1)/2 = add from 0 to n
  public static int func(int n) {
    if (n==0)
      return 0;
    else
      return n + func(n-1);
  }
}

3-1) 예제 3의 증명 - 순환함수와 수학적귀납법

 - func(int n)은 음이 아닌 정수 n에 대해서 0에서 n까지의 합을 올바로 계산한다.

 

증명{

 1) n=0인 경우 : n=0인 경우 0을 반환한다. 올바르다.

 2) 임의의 양의 정수 k에 대하여 n < k인 경우 0에서 n까지의 합을 올바르게 계산하여 반환한다고 가정.

 3) n=k인 경우 : func은 먼저 func(k-1)을 호출하는데 2번의 가정에 의해서 0 ~ k-1의 합이 올바로 계산되어 반환된다. 메서드 func은 그 값에 n을 더해서 반환한다. 따라서 메서드 func은 0에서 k까지의 합을 올바로 계산하여 반환한다.

 

1-1 Factorial : n!

 - 0! = 1

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

 

package inflearn.chapter2.recurtion;

// Factorial : n!
public class RecursionEx4 {
	public static void main(String[] args) {
      
	}
	
	public static int factorial (int n) {
		
	  if (n == 0)
	    return 1;
	  else
	    return n * factorial(n - 1);
	}
}

 

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

 - recursion을 이용하여, x^n값 구현 (x^n : x의 n제곱)

 - x^n값을 구하기 위해 x^0 ( = 1) 값 부터 x^(n-1)값 까지 차례대로 구한 뒤 마지막에 x를 곱하여 x^n과 같게 만듬.

 

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

1-3 Fibonacci Number

 - f0 = 0

 - f1 = 1

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

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

 

1-4 최대공약수 : Euclid Method

	// find greatest common denominator
	public static double gcd(int m, int n) {
	  if (m < n) {
	    int tmp = m; m = n; n = tmp; // swap m and n
	  }
	  if (m % n == 0)
	    return n;
	  else
	    return gcd(n, m%n);
	}

1-5 최대공약수 간단화 

 - 1-4의 코드에서 m과 n을 swap하는 과정을 삭제 (else단계에서 swap실행)

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