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)라는 최적화 형태도 있다.

• 작성규칙

  • 종료조건은 먼저쓰기: 문제조건의 함수적 표현이라는 점에서 앞에 쓰는것이 문제의 형태를 정의하고 알아보기도 쉬우며 햇갈리지 않는다.

재귀와 반복문 비교

• 두가지 핵심요소
  • 재귀호출(Recursive Call)
  • 종료조건(Base Case)
• 콜스택
  • 가장위 !1 / !2 / !3/ !4/ !5 가장 아래
  • 재귀 = 콜스택
  • 재귀로 풀 수 있는것은 스택과 반복문으로 가능
  • 어느쪽이 더 효율적인지는 상황에 따라 다름
• 종료 조건이 없으면?
  • 스택 오버플로우
    • 콜스택 보통 1-8MB
    • 프레임 하나: 수십~수백 바이트
      • 약 10000번 재귀 호출이면 위험할 수 있음
• 작성 규칙
  1. 종료조건은 먼저 쓰기

      int factorial(int n) {
          if (n <= 1) return 1;
          return n * factorial(n - 1); // - 재귀 호출은 그 다음
          // ← 종료 조건 먼저!
      }
     

• 재귀적 사고의 핵심 질문
  • 같은 문제의 작은 버전으로 표현이 가능한가?
    • 피보나치: 재귀의 교과서같은 문제, 하지만 함정

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

      • 특정 단계의 재귀호출 가능 ->비효율적, 동적 프로그래밍 필요.
    • 거듭제곱
      • 단순재귀도 가능하고, 분할정복도 가능
    • 이진탐색
• 재귀 vs 반복문 | 재귀 | 반복문 | |–|–| |트리/그래프 탐색 | 단순 합/ 카운팅 | |분할정복(병합정렬)|–| |순열/조합 생성|–| |구조 자체가 재귀적일때|–|
  • 재귀는 문제는 줄이면서 반복
  • 반복문은 순서대로 반복
  • 완전탐색, 그래프에서는 재귀가 더 효율적
• 꼬리 재귀(Tail Recursion)
• 실전에선?
  • 게임에서의 많은 재귀적 구조
    • 행동트리(Behavior Tree)
    • 프랙탈 지형 생성 - 재귀로 지형을 세분화
    • 파티클 시스템 - 분기구조
  • 웹서버
    • JSON 파싱
    • 파일 시스템 탐색 - 폴더 안에 폴더 안에 …
    • DOM 트리 순회: HTML
  • CS
    • 수학적 귀납법-> 알고리즘의 증명
    • 함수형 언어 - 반복문보단 재귀
    • 컴파일러
    • 그래프/트리 탐색