순환(Recursion)의 개념, 기본예제1

uglyduck.dev·2020년 9월 20일
algorithm
0

알고리즘 🧮

목록 보기
1/16

순환(Recursion)의 개념

자기 자신을 호출하는 함수 혹은 메서드(=재귀함수)

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

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

  • main에서 func()를 호출한다 -> "Hello..."를 출력한다 -> 다시 func()를 호출한다 ... -> "Hello..."를 호출한다

  • 너무나도 당연하게 무한 루프에 빠질 수 있다.

Q. recursion은 항상 무한루프에 빠질까? 

public class Code02{
  public static void main(String [] args){
    int n = 4;
    func(n);
  }
  
  public static void func(int k){ // 매개변수 k
    if(k<=0)  // 매개변수 0이하라면 (음수)
      return; // 자기 자신을 호출하지 않는다(종료).
    else {    // 0보다 큰 경우(양수)
      System.out.println("Hello...");
      func(k-1);  // 인자값을 1만큼 감소시켜준다.
    }
  }
}
  • recursion이 적절한 구조를 가지고 있다면 recursion이 항상 무한루프에 빠지지 않는다.

무한루프에 빠지지 않기 위한 전제조건

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

if (k<=0)
  return;

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

func(k-1);

=> Base case와 Recusive case의 두 가지 전제조건이 성립되어야 무한루프에 빠지지 않는다.

  • 둘 중 어느 하나라도 적절한 구조를 가지지 않는다면 원하는 결과 값이 나오지 않을 수 있다.

구현 예시

0에서 n까지의 합을 구하라.

public class Code01{
  public static void main(String [] args){
    int result = func(4);
    System.out.print(result);
  }
  
  public static void func(int n){
    if(n==0) // n=0이라면 합은 0이다.
      return 0; 
    else {  
      return n+func(n-1); 
      // func(n-1)메서드를 호출하고 n만큼 더 해준다. 1~n가지의 합을 구한다.
      // n이 0보다 크면 0에서 n까지의 합은 0에서 n-1까지의 합에 n을 더한 것이다.
    }
  }
}

Factorial: n! (1에서 n까지의 곱)

0! = 1

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

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

Xn(X의 n승 구하기)

X0 = 1

Xn = X*Xn-1       if n>0

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

Fibonacci Number

f0 = 0

f1 = 1

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

public int fibonacci(int n){ // n이 음수가 아니라는 것을 가정했을 때
  if(n<2)
    return n;
  else
    return fibonacci(n-1) + fibonacci(n-2);
}

최대공약수: Euclid Method

public static int gcd(int m, int n){
  if(m<n){   // m값이 n보다 작을 경우
    int tmp=m; m=n; n=tmp;  // m과 n을 swap한다
  }
  if(m%n==0) // m이 n으로 나누어서 떨어지는 값이 0이라면 최대공약수이다.
    return n;
  else       // m이 n으로 나누어 떨어지지 않는다면, n값과 m을 n으로 나눈 나머지 간의 최대공약수와 동일하다.
    return gcd(n, m%n);
}

=> m≥n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n)=n이고, 그렇지 않으면 gcd(m,n)= gcd(n,m%n)이다.

Reference

profile
uglyduck.dev
시행착오, 문제해결 그 어디 즈음에.
다음 포스트

순환(Recursion)의 개념, 기본예제2

0개의 댓글