[Recursion] 간단한 예제

Factorial: n!

• 0~n까지의 곱
• 정의

  0! = 1               (n=0)

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

예제 Factorial.java

factorial(int n) 

1~n 까지의 곱

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

 

x^n

• x의 n승
• 정의

  x^0 = 1                (n=0)

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

예제 Power.java

power(double x, int n) 

1~n 까지의 곱

public class Power{
  public static void main(String[] args){
    int result = power(2, 4);
    System.out.print(result);
  }
 
  public static double power(double x, int n){
    if (n==0){
      return 1;
    }else{
      return x * power(x, n-1);
    }
  }
}

 

Fibonacci Number

• 피보나치 수열
• 정의

  f(0) = 0                      (n=0)

  f(1) = 1                      (n=1)

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

예제 Fibonacci.java

fibonacci(int n) 

피보나치 수열

public class Fibonacci{
  public static void main(String[] args){
    int result = fibonacci(4);
    System.out.print(result);
  }
 
  public static int fibonacci(int n){
    // n은 음수가 아니라고 가정한다. 
    if (n<2){
      return n;
    }else{
      return fibonacci(n-1) + fibonacci(n-2);
    }
  }
}

 

최대공약수 : Euclid Method

• 0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수.
• 정의

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

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

예제 Gcd.java

gcd(int m, int n) 

최대공약수 구하기.

public class Gcd{
  public static void main(String[] args){
    int result = gcd(10, 12);
    System.out.print(result);
  }
 
  public static int gcd(int m, int n){
    // m이 n보다 크다고 가정했기 때문에 m이 n보다 작은 경우 스왑해준다. 
    if (m<n){
      int tmp = m;
      m=n;
      n=tmp;
    }
 
    if(m%n == 0)
      return n;
    else
      return gcd(n, m%n);
  }
}

조금 더 단순한 버전의 Euclid Method

• 정의

  gcd(p,q)에서

  p                    (if q=0)

  gcd(q, p%q)      (otherwise)

• p가 반드시 q보다 클 필요가 없다.

예제 Gcd02.java

gcd(int p, int q) 

조금 더 단순한 최대공약수 구하기.

public class Gcd02{
  public static void main(String[] args){
    int result = gcd(10, 12);
    System.out.print(result);
  }
 
  public static int gcd(int p, int q){
    if(q==0)
      return p;
    else
      return gcd(q, p%q);
  }
}

무한루프에 빠지지 않는 이유는?

출처

https://www.youtube.com/watch?v=ln7AfppN7mY&list=PL52K_8WQO5oUuH06MLOrah4h05TZ4n38l&index=1