C++: 재귀(Recursion)

• 재귀(Recursion)

  • 반복을 구현하는 한 형태로 반복문과는 다르개 스스로를 다시 호출하는 행위를 통해 구현하는 방법이다. 함수의 형태로 함수가 스스로를 다시 호출하는 자기호출/재귀호출(Recursive Call)과 호출의 반복을 끊어줄 조건인 바닥상태(Base Case)로 이루어진다.
  • 문제의 상태를 함수로 바로 표현함으로서 문제의 작은 버전으로 표현될 수 있으며, 재귀가 적합한 경우에는 반복문으로 해결할 때 보다 직관적이고 간결한 경우가 많다.
    • 하지만 많은 반복을 실행해야 하는 경우 스택 오버플로우(Stack Overflow)문제에 노출되게 된다.
    • 그리고 필연적으로 재귀의 형태가 문제의 표현에 적합한 것 또한 아니다.
  • ex) 팩토리얼
    • 5호출 -> 4호출 -> 3호출 -> 2호출 -> 1호출 (BaseCase)
    • 5반환 <- 4반환 <- 3반환 <- 2반환 <- 1반환
  • 함수의 호출은 콜스택(Call Stack)에 쌓이게 되며, 가장 늦게 호출, 죽 콜스택에 가장 늦게 삽입된 재귀함수의 끝인 바닥상태부터 돌아오면서 전체 계산의 결과를 만들어내게 된다.
    • 바닥상태를 확인한 후 다시 돌아오는 과정이 필요 없이 반환하며 종료되는 꼬리재귀(Tail Recursion)라는 최적화 형태도 있다.
  • 종료조건은 먼저쓰기: 문제조건의 함수적 표현이라는 점에서 앞에 쓰는것이 문제의 형태를 정의하고 알아보기도 쉬우며 햇갈리지 않는다.

• 재귀적 사고

  • 재귀의 핵심은 문제의 형태를 함수로 그대로 표현하는 것이다.
    • 같은 문제의 작은 버전으로 표현이 가능한가?
    • 피보나치
      • 재귀의 교과서같은 문제이지만, 단순재귀로 풀게되면 같은 값을 여러번 계산하고, 시간복잡도가 커지는 되는 문제를 가진다.
        • ex- 피보나치 4번째를 재귀로 계산하면 2번째 수만 2번 따로 계산해야된다.
        • 이는 계산 결과를 기억하여 후에도 다시 사용하는 동적 프로그래밍(Dynamic Programming, DP)를 적용하면 더 효율적으게 된다.

            int fib(int n) {
            if (n <= 1) return n;
            return fib(n - 1) + fib(n - 2);
            }
          

      • 특정 단계의 재귀호출 가능 ->비효율적, 동적 프로그래밍 필요.
    • 배열의 합
      • 보통은 For문으로도 구현하는게 좋지만, 재귀로도 가능하다.
        • 지금 예시는 배열만 넘길 수 있도록 만들었지만, 인덱스까지 넘기고 배열은 참조로 넘기도록 하는편이 더 메모리 효율적이긴 할것이다.

            int sum(vector<int> a) {
            if (a.empty()) return 0;
            int num = a.back();
            a.pop_back();
            return num + sum(a);
            }
          

    • 거듭제곱
      • 단순재귀도 가능하고($O(n)$), 분할정복도 가능($O(log n)$)

          int power(int base, int exponent) {
          if (exponent == 1) return base;
          return base * power(base, exponent - 1);
          }
        

          int power(int base, int exponent) {
          if (exponent == 0) return 1;
          int half = power(base, exponent / 2);
          if (exponent % 2 == 0)
              return half * half;
          else
              return base * half * half;
          }
        

    • 이진탐색
      • 이진트리, 탐색 문제등에서 두루 쓰인다.

• 재귀 vs 반복문

  재귀가 우위	반복문이 우위
  탐색	단순 합/카운팅
  분할정복(병합정렬)	n회 반복
  순열/조합 생성	스택 오버플로우 우려
  구조 자체가 재귀	단순 반복

  • 재귀는 문제는 줄이면서 반복
  • 반복문은 순서대로 반복
  • 완전탐색, 그래프에서는 재귀가 더 효율적

• 사용 예시

  • 게임에서의 많은 재귀적 구조
    • 행동트리(Behavior Tree)
    • 프랙탈 지형 생성 - 재귀로 지형을 세분화
    • 파티클 시스템 - 분기구조
  • 웹서버
    • JSON 파싱
    • 파일 시스템 탐색 - 폴더 안에 폴더 안에 …
    • DOM 트리 순회: HTML
  • CS
    • 수학적 귀납법-> 알고리즘의 증명
    • 함수형 언어 - 반복문보단 재귀
    • 컴파일러
    • 그래프/트리 탐색