[Algorithm] 순환(Recursion)

순환 = 재귀

 

자기 자신을 호출하는 함수 = 재귀함수 = 순환 

 

* 예시

int main() {
  int result = func(4);
}
int func(int n) {
  if (n==0)
    return 0;
  else
    return n + func(n-1);
}

1~n까지의 합을 구한다.

무한루프에 빠지지 않으려먼 조건(base case)을 걸어주어야 함. 하지만 base case가 있다고 하여 모든 재귀함수가 종료되는 것은 아님.

=> recursion을 반복하다보면 결국 base case로 수렴해야 한다. (이 조건을 함께 만족해야 무한루프에 빠지지 않는다.)

return하여 재귀를 빠져나오게 되면 마지막으로 실행했던 문장으로 돌아간다.

 

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

4로 호출하면 10이 출력된다.

 

* 동작

 

 

* factorial

0! = 1

n! = n×(n-1)!     if(n>0)

int factorial(int n) {
    if (n==0)
       return 1;
    else
       return n * factorial(n–1);
}

 

* factorial(4)의 동작

 

* x의 n승

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

시간복잡도: O(n)

 

* 피보나치

f0 = 0
f1 = 1
fn = fn-1 + fn-2     if(n>1)

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

 

* 최대공약수

유클리드 메소드 이용

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 

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

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

 

조금 더 단순하게 바꾸기

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

 

---

 

*  문자열의 길이 계산

int length(char *str) {
  if (*str == ‘\0’)
    return 0;
  else
    return 1 + length(str+1);
}

 

 

 

* 문자열 뒤집기

void printCharsReverse(char *str) {
    if (*str==‘\0’)
        return;
    else {
        printCharsReverse(str+1);
        printf(“%c”, *str);
    }
}

//Java
if(str.length()==0)
   return 0;
else {
   printCharsReverse(str.substring(1));
   sysout(str.charAt(0));
}

 

* 순차탐색

data[0]에서 data[n-1] 사이에서 target을 검색한다.

존재하면 배열 인덱스, 존재하지 않으면 -1을 반환한다.

int search(int data[], int n, int target,) {
    if (n <= 0)
        return -1;
    else if (target==items[n-1])
        return n-1;
    else
        return search(data, n-1, target);
}

 

* 최대값 찾기

int findMax(int n, int data[]) {
   if (n==1)
      return data[0];
   else
      return max(data[n-1], findMax(n-1, data));
}

 

*  Recursion vs. Iteration

모든 순환함수는 반복문(iteration)으로 변경 가능 => 그 역도 성립함.

즉 모든 반복문은 recursion으로 표현 가능함
순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것을 가능하게 함

하지만 함수 호출에 따른 오버헤드가 있음 (매개변수 전달, 액티베이션 프레임 생성 등) => 속도 면에서는 손해일 수 있음

 

---

 

순환적 알고리즘의 설계

 

1. 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸기!

=> 암시적으로 선언하면 처음 호출할 때는 문제가 없으나, 재귀적으로 호출할 경우 문제 발생

BUT, end같은 경우는 변하지 않으므로 암시화해도 괜찮다.

(아래 코드에서 암시적으로 선언된 경우는 매개변수에 int being 이 부분이 int 0으로 선언된 경우)

2. 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함 + 모든 case는 결국 base case로 수렴해야 함

 

 

* 이진 탐색: Iterative Version

int binarySearch(int data[], int n, int target) {
   int begin = 0, end = n-1;
   while (begin<=end) {
      int middle = (begin+end)/2;
      if (data[middle] == target)
         return middle;
      else if (data[middle] > target)
         end = middle - 1;
      else
         begin = middle + 1;
   }
   return -1;
}

 

* 이진탐색: Recursion

items[begin]에서 items[end] 사이에서 target을 검색한다.

int binarySearch(int data[], int target, int begin, int end)  {
    if (begin>end)
      return -1;
    else {
        int middle = (begin+end)/2;
        if (data[middle] == target)
            return middle;
        else if (data[middle] > target)
            return binarySearch(data, target, begin, middle-1);
        else
            return binarySearch(data, target, middle+1, end);
    }
}

- 자바 코드

 

*  2-SUM

data[begin]에서 data[end] 사이에서 합이 K가 되는 쌍이 존재하는지 검사한다.

데이터는 오름차순으로 정렬되어 있다고 가정한다.

bool twoSum(int data[], int begin, int end, int K)  {
   if (begin>=end) //만약 중복 선택이 가능하다면 =을 빼면 됨
      return false;
   else {
      if (data[begin]+data[end] == K)
         return true;
      else if (data[begin]+data[end]<K)
         return twoSum(data, begin+1, end, K);
      else
         return twoSum(data, begin, end-1, K);
   }
}