알고리즘- 순환(recursion)의 개념과 예제

알고리즘- 순환(recursion)의 개념과 예제

> 알고리즘의 기본이 되는 recursion 에 대해서 알아보자.

public class code{
  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");
      func(k-1);
    }
  }
}

무한루프에 빠지지 않으려면? (recursion이 갖춰야 할것)
if(k<=0)에 해당하는 부분은 Base case라 하고, 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야한다.func(k-1)에 해당하는 부분은 Recursive case라 하고, recursion을 반복하다보면 결국 base case로 수렴해야 한다.
| 기본적인 recursion 함수 예제
1.합 구하기

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

1~n 까지의 합을 구하는 가장 기본적인 recursion 함수
이안에 담겨있는 순환함수와 수학적 귀납법

정리: 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까지의 합을 올바로 계산하여 반환한다.

2. Factorial
factorial에 대해서 알아보기에 앞서, factorial을 아래와 같이 정의해보자. (n!)

0!=1
​
n!=nx(n-1)!   n>0

아래는 팩토리얼 함수이다.

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

팩토리얼 역시 순환함수와 수학적 귀납법으로 해석해보자.

정리:factorial(int n)은 음이 아닌 정수 n에 대해서 n!을 올바로 계산한다.

증명:

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

2. 임의의 영의 정수 k에 대해서 n<k인 경우 n!을 올바르게 계산한다고 가정하자.

3. n=k인 경우를 고려해보자. factorial은 먼저 factorial(k-1) 호출하는데 2번의 가정에 의해서 (k-1)!이 올바로 계산되어 반환된다. 따라서 메서드 factorial은 k*(k-1)=k!을 반환한다.

3. power 함수 n제곱*n-1제곱*...*1

x의 0제곱=1

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

4. 피보나치

f0=0

f1=1

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

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

5. 최대공약수 (euclid method)

public static int 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);
}

• 좀더 단순한 버전의 euclid method

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