Chapter 1. 재귀(Recursion) : 개념과 기본 예제들

권오흠 교수님의 유튜브 강의 영리한 프로그래밍을 위한 알고리즘 강좌 를 듣고 정리한 필기입니다. 😀

Chapter1. Recursion

🔔 Recursion

Recursion : 자기 자신을 호출 하는 함수 = 재귀 함수

무한 루프에 빠지지 않으려면

• 재귀 함수는 자기 자신을 호출하기 때문에 무한 루프에 빠질 수 있다.
  • 따라서 적어도 하나의 더 이상 자기 자신을 또 호출하지 않는 종료 Case가 존재해야 한다.

int main() 
{
    int result = func(4);
}

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

• 위 코드에서의 종료 조건 👉 n == 0
  • return n + func(n-1);
    • n + 1이였다면 무한 루프.
    • 종료 조건인 n = 0 에 수렴하도록 n 이 작아지는 방향으로 구조를 짜야 한다.
• 호출 과정은 “C++ 재귀적 함수 호출” 포스트 참고

재귀 함수와 수학적 귀납법

정리 : func(int n)은 음이 아닌 정수 n에 대해서 0에서 n 까지의 합을 올바로 계산한다.

• 증명
  1. n = 0인 경우 👉 n=0인 경우 0을 반환한다 ⭕
  2. n < k인 경우 👉 임의의 양의 정수 k에 대해서 n < k인 경우 0에서 n 까지의 합을 올바르게 계산하여 반환한다고 가정.
  3. n = k인 경우 👉 func은 먼저 func(k-1) 호출하는데 2번 가정에 의해서 0에서 k-1까지의 합이 올바로 계산되어 반환된다. 메서드 func은 그 값에 n을 더해서 반환하므로 결국 0에서 k까지의 합을 올바로 계산하여 반환한다. ⭕
     • func(k) = k + func(k-1) 에서 2 번 가정에 의해 func(k-1)가 올바르므로 func(k)도 올바름.

재귀 Vs. 반복

모든 재귀 호출은 반복문으로 변경 가능하며 그 역으로도 성립한다. 모든 반복문은 재귀 호출로도 변경 가능하다.

• 재귀 함수
  • 장점 : 복잡한 알고리즘을 사람이 보기에 단순하고 알기 쉽게 표현 가능
  • 단점 : 함수 호출에 따른 오버헤드가 있음

재귀 알고리즘 설계

뒤에서부터 빠져나오면서, 혹은 더 깊이 들어가고 차례로 빠져나오면서 뭘 하고 싶을 때.

• 적어도 하나 이상의 순환되지 않는 종료 case가 있어야 한다.
• 모든 case는 종료 case로 수렴해야 한다.
• 암시적 매개변수를 명시적 매개변수로 바꿔라
  • 재귀 호출을 위해 매개변수를 좀 더 일반화 하란 얘기

🔔 재귀 함수를 사용하는 알고리즘

팩토리얼 n!

시간 복잡도 O(n)

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

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

\(X^n\)

시간 복잡도 O(n)

• \(X^0 = 1\)
• \(X^n = X * X^{n-1}\)

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

피보나치 수열

\[f_0 = 0\] \[f_1 = 1\] \[f_n = f_{n-1} + f{n_2}\]

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

중복 계산이 너무 많아서 재귀로 푸는건 비효율적이다.

f(4) = f(3) + f(2) = f(1) + f(2) + f(1) + f(0) = f(1) + f(1) + f(0) + f(1) + f(0)

• 중복 多

최대공약수 구하기 Euclid Method

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

• m >= n 인 두 양의 정수 m 과 n 에 대해서
  • if (m%n==0)
    • m 이 n 의 배수이면 gcd(m, n) = n 이고,
      • 리턴하는 이 n 이 최대 공약수가 된다.
      • 종료 조건
  • else
    • 그렇지 않으면 gcd(m, n)= gcd(n, m%n) 이다.
      • 재귀
• ex) 15 와 6 의 최대 공약수는
  • gcd(15, 6) 👉 gcd(6, 3) 호출 👉 3 리턴.

더 간단한 버전

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

• ex) 15 와 6 의 최대 공약수는
  • gcd(15, 6) 👉 gcd(6, 3) 호출 👉 gcd(3, 0) 호출 👉 3 리턴.
  • 위 예제와 다르게 gcd(3, 0) 까지 간다.

문자열

길이 계산

💡 현재 문자열 길이 = 첫번째 문자를 제외한 문자열의 길이 + 1

• 💡 재귀적 아이디어
  • “abcde” 라는 문자열의 길이를 잰다면
    • “abcde”.length = “bcde”.length + 1
    • “bcde”.length = “cde”.length + 1
    • “cde”.length = “de”.length + 1
    • “de”.length = “e”.length + 1
    • “e”.length = “\0”.length + 1
    • “\0”.length = 0 👈 종료조건
  • 결론적으로 “abcde”.length = 0 + 1 + 1 + 1 + 1 = 5 가 된다.

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

• char 포인터 str가 문자열 배열의 주소를 담게 되면
  • str+1은 다음 원소를 가리키므로 다음 원소를 시작점으로 하는 배열을 뜻하게 된다.

length(str) = 1 + length(str+1)

프린트

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

거꾸로 프린트

💡 문자열 거꾸로 프린트 = 첫번째 문자를 제외한 문자열 거꾸로 프린트 + 이후 첫번째 문자 맨 뒤에 프린트

void printCharsReverse(char * str) 
{
    if (*str==‘\0’)
        return;
    else 
    {
        printCharsReverse(str+1);
        printf(“%c”, *str);  // %c 로 받으므로 한글자만 출력. *str 즉 첫번째 문자 
    }   
}

• 마지막 끝 문자까지 끝까지 들어간 이후에 빠져 나오는 과정에서 한문자씩 print
  • 즉 뒷글자부터 한문자씩 출력하게 된다.
  • 👉 재귀 호출 printCharsReverse(str+1)가 printf 보다 앞에 있어야 한다.
  • printCharsReverse(“abcde”)
    • printCharsReverse(“bcde”) 호출
      • printCharsReverse(“cde”) 호출
        • printCharsReverse(“de”) 호출
          • printCharsReverse(“e”) 호출
            • printCharsReverse(“\0”) 호출
            • return 후 e 출력
          • return 후 d 출력
        • return 후 c 출력
      • return 후 b 출력
    • return 후 a 출력

순차 탐색

data[0] ~ data[n-1] 사이에서 target이 있는지 검색한다. 존재하면 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);  // 👈
}

• 인덱스 0 부터 시작으로 쳐서 (즉 배열 원소 전체) begin, end 인덱스는 넘길 필요 X
• 💡 재귀적 아이디어
  • 주어진 범위에서 마지막 원소가 target과 동일한지 검사
    • 원소 하나하나씩 전부 검사하게 됨 👉 순차 탐색
  • ex) n = 5 이고 data[1]이 target일 때.
    • search(5) 👉 data[4]가 target인지 검사
      • search(4) 👉 data[3]가 target인지 검사
        • search(3) 👉 data[2]가 target인지 검사
          • search(2) 👉 data[1]가 target인지 검사
            • 1 을 리턴한다. (search(2))
          • 1 을 리턴한다. (search(3))
        • 1 을 리턴한다. (search(4))
      • 1 을 리턴한다. (search(5))

최대값 찾기

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

💡 data[0] ~ data[n-1] 사이에서의 최대값 = data[0] ~ data[n-2] 사이에서의 최대값 과 data[n-1] 中 더 큰 값.

• 인덱스 0 부터 시작으로 쳐서 (즉 배열 원소 전체) begin, end 인덱스는 넘길 필요 X
• ex)
  • findMax(5, data) 👉 findMax(4, data) 과 data[4] 중에 큰 값
    • findMax(4, data) 👉 findMax(3, data) 과 data[3] 중에 큰 값
      • findMax(3, data) 👉 findMax(2, data) 과 data[2] 중에 큰 값
        • findMax(2, data) 👉 findMax(1, data) 과 data[1] 중에 큰 값
          • findMax(1, data)
          • data[0] 리턴
        • data[0] , data[1] 중에 큰 값 리턴
      • data[0] ,data[1], data[2] 중에 큰 값 리턴
    • data[0] ,data[1], data[2], data[3] 중에 큰 값 리턴
    • data[0] ,data[1], data[2], data[3], data[4] 중에 큰 값 리턴

int findMax(int data[], int begin, int end) 
{
    if (begin == end)
        return data[begin];
    else
    {
        int middle = (begin + end) / 2;
        int max_1 = findMax(data, begin, middle);
        int max_2 = findMax(data, middle + 1, end);

        return max(max1, max2);
    } 
}

• 전체 배열이 아닌 구체적인 범위가 주어진 경우기 때문에 시작 인덱스와 끝 인덱스를 넘겨주었다.
• 💡 재귀 호출이 전부 끝난 최종적인 max_1과 max_2 값끼리 비교한게 진짜 최대값이다.

10진수 정수를 2진수로 변환하여 출력

void printInBinary(int n)
{
    if (n < 2) // 종료조건
        printf("%d", n);  
    else
    {
        printInBinary(n / 2);  // 👈
        printf("%d", n % 2);
    }
}

• 💡 2 로 나눈 나머지가 0 혹은 1이 될 때까지 계속 해서 2 로 나눈 몫을 또 2로 나누고 반복
• 💡 나머지들을 출력하되 출력은 역순으로 해야하므로 재귀호출이 모두 끝난 다음에 printf 출력할 수 있도록 printf를 재귀 호출보다 뒤에 위치하게
  • ex) n = 13
    • printInBinary(13)
      • 👉 printInBinary(6)
        • 👉 printInBinary(3)
          • 👉 printInBinary(1)
            • 1 출력
          • 1 출력 (3 % 2)
        • 0 출력 (6 % 2)
      • 1 출력 (13 % 2)
    • 최종적으로 1101 출력

Disjoints Set

A, B 두 배열의 교집합, 즉 공통 원소가 하나도 없으면 True, 하나라도 있으면 False

A, B 두 배열이 정렬되어 있다고 가정

bool isDisjoint(int m, int A[], int n, int B[])
{
    if (m<0 || n<0)   // 종료조건 1️⃣ 공통 원소가 하나도 없음. Disjoint 함.
        return true;
    else if (A[m-1]==B[n-1]) // 종료조건 2️⃣ 공통 원소 발견. Disjoint 하지 않음.
        return false;
    else if (A[m-1]>B[n-1])
        return isDisjoint(m-1, A, n, B);  // 👈
    else
        return isDisjoint(m, A, n-1, B); // 👈
}

• 💡 끝 원소부터 차례대로 검사해나간다.
  • A[m-1]>B[n-1] 라면 A[m-1]은 모든 B[0] ~ B[n-1] 들 보다 크다.
    • A, B 두 배열은 정렬되어 있기 때문에.
    • 따라서 A[m-1]은 B[0] ~ B[n-1] 범위 내엔 없으므로 A 의 다음 안쪽 원소 검사. 재귀로 다음 원소로 들어가기
      • 👉 재귀 호출 : 이제 A[m-2] 와 B[n-1] 비교
        • isDisjoint(m-1, A, n, B)
  • A[m-1]<B[n-1] 라면 B[n-1]은 모든 A[0] ~ A[m-1] 들 보다 크다.
    • A, B 두 배열은 정렬되어 있기 때문에.
    • 따라서 B[n-1]은 A[0] ~ A[m-1] 범위 내엔 없으므로 B 의 다음 안쪽 원소 검사. 재귀로 다음 원소로 들어가기
      • 👉 재귀 호출 : 이제 B[n-2] 와 A[m-1] 비교
        • isDisjoint(m, A, n-1, B)
  • 두 배열 중 하나라도 인덱스가 음수가 되면 종료. 한 배열을 다 뒤졌는데도 공통 원소가 없는 것이니!

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Algorithm Lesson 1 카테고리 내 다른 글 보러가기