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

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

 

Recursion = 순환 = 재귀함수 > 스스로를 호출하는 함수

 

무한 루프에 빠지지 않는 조건

1. Base Case: 적어도 1개의 순환이 존재하지 않는 경우 존재한다.

2. Recursive Case: 순환을 반복하다보면 Base Case로 수렴한다.

 

순환 알고리즘 예제)

 

최대공약수: Euclid Method

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

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

 

public static double gcd(int m, int n) {
   if (m < n) {
      int tmp = m;
      m = n;
      n = tmp;
   }
   if (m % n == 0)
      retrun n;
   else
      return gcd(n,m % n);
}

public static double gcd(int p, int q) {
   if (q == 0)
      return p;
   else
      return gcd(q,p%q) //왜 순환에 빠지지 않나 생각해보기.
}

 

<영리한 프로그래밍을 위한 알고리즘 강좌 - 권오흠 교수님>

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C#description