내일배움캠프 47일차 - 자료구조 & 알고리즘 8주차 : 재귀

 재귀

 - 함수가 자기 자신을 호출하는 것을 일컫는다.
예) 팩토리얼(Factorial)

재귀가 동작하기 위해서는 두 가지 조건이 필요하다.

1) 재귀호출: 자기 자신을 호출하되, 종료지점에 가깝게 문제가 작아진다.
2) 종료조건(Base case): 더이상 호출하지 않는 지점

내려가면서 호출하고, base case(돌아오는 값)을 만나면
거슬러 올라오면서 계산한다.

재귀 함수는 우리가 직접 스택을 만들지 않아도 자동으로 콜 스택을 사용한다.
 - 재귀로 풀 수 있는 것 = 스택 + 반복문으로도 풀 수 있다.
 - 재귀가 더 깔끔할 때가 있고, 반복문이 더 효율적일 때가 있다.

종료 조건이 없으면 발생하는 문제 - 무한 호출

위 사진처럼 재귀호출을 하지않는 시점이 없으면 무한호출이 발생한다.
호출이 지나치게 잦으면(약 1만번 초과) 콜 스택 메모리(보통 1~8MB)가 가득하게 되어 프로그램 크래시가 발생한다.

이를 스택 오버플로우(Stack Overflow)라고 한다.

무한 호출을 방지하기 위해
재귀 전 종료 조건(base case)를 작성해야 한다.

재귀 사용 예시

피보나치 수열 (재귀의 함정)

F(4)의 호출 트리. 빨강 = 중복 호출 / 초록 = base case (멈춤)

피보나치 수열 F(n)의 값을 구하려면 F(n-1)와 F(n-2)의 값이 필요하다.

하지만 재귀로 호출을 반복하는 과정에서 F(2)가 두 번, F(1)이 3번 호출이 된다. 만약 재귀 시작 값이 지금보다 높아지면 F(2)가 중복 호출되는 횟수가 기하급수적으로 높아질 것이다.

F(n)에서 함수가 호출되는 횟수

같은 값을 중복 호출, 계산하기 때문에 n이 높을 수록 호출 횟수가 기하급수적으로 올라간다.

이 때문에 재귀는 항상 효율적으로 해결되지 않으며, 이를 해결하려면 훗날 배울 DP(동적 프로그래밍)가 필요할 것이다.

배열의 합 (재귀적 분해)

배열 [1,2,3,4,5]의 합을 재귀로 구해봅시다.

핵심: 전체 합 = 첫 번째 원소 + 나머지의 합

거듭제곱 - "어떻게 나누느냐"가 효율을 바꾼다

2^10을 재귀로 구하는 방법에는 두 가지가 있다.

단순 재귀
 : 2^10 = 2×2^9
 : 2^9 = 2×2^8
 : 2^8 = 2×2^7
 : ...
 : 2^1 = 2
→ 10번 호출 = O(n)

분할 정복 재귀
 : 2^10 = (2^5)^2
 : 2^5 = 2×(2^2)^2
 : 2^2 = (2^1)^2
 : 2^1 = 2
→ 약 4번 호출 = O(log n)

7주차에서 배웠던 분할 정복의 위력이 재귀에서도 똑같이 작동한다.

한 번에 하나 씩 줄이느냐 vs 절반으로 줄이느냐의 차이.

재귀 vs 반복문

재귀로 풀 수 있는 것은 이론적으로 반복문으로도 풀 수 있다.

재귀로 풀기 좋은 경우
 : 트리/그래프 탐색
 : 분할 정복 (병합 정렬)
 : 순열/조합 생성
 : 구조 자체가 재귀적일 때
→ "문제를 줄이며 반복" (전체 = 작은부분 + 나머지)

반복문이 나은 경우
 : 단순 합 / 카운팅
 : 1~n 순회
 : 스택 메모리 걱정 시
 : 구조가 단순한 반복
→ "순서대로 반복" (앞에서부터 하나 씩)

※ 재귀와 반복문도 도구 선택의 문제이다.

※ 10주차의 완전 탐색이나 Level5 그래프 등 재귀가 필요한 문제가 자주 등장한다.

---

CS 돋보기

스택 프레임 - 함수의 대기실

컴퓨터는 함수를 호출하면 '지금 하던 일'을 저장하고 새 함수로 이동한다.

이때 저장되는 것을 스택 프레임(Stack Frame)이라고 한다.

스택 프레임에 담기는 것
 : 매개 변수 (이 호출에서의 n값)
 : 지역 변수
 : 돌아올 주소 (이 함수가 끝나면 어디로 돌아가는가?)

재귀에서는 같은 함수의 스택 프레임이 여러 개 쌓인다.

같은 함수이지만 n이 다른 "별개의 실행 환경"인 것이다.

같은 함수라도 n이 다른 별개의 실행 환경.
결과값 "?"는 base case에서 값이 돌아올 때 채워진다.

각 스택 프레임: 수십~수백 바이트
콜 스택 크기: 보통 1MB (Windows 기본값), 최대 8MB

1MB / 100 바이트  = 약 10,000번 재귀 호출 가능

 → 재귀 깊이가 1만을 넘으면 위험 신호. 깊이가 예측 불가능하거나 매우 깊어진다면 반복문으로 변환하는 것을 고려해야 한다.

꼬리 재귀

재귀 호출이 함수의 마지막 동작일 때, 이를 꼬리 재귀라고 한다.

이 경우 컴파일러가 재귀를 반복문으로 자동 변환할 수 있어서 스택이 쌓이지 않는다. (꼬리 호출 최적화, TCO)

C++에서는 컴파일러와 최적화 레벨에 따라 지원 여부가 다르다.

※ 크게 중요하지 않으나, "재귀가 항상 스택을 많이 쓰는 것은 아니다" 라는 사실.

실전에서는?

게임 개발

게임 AI의 행동 트리(Behavior Tree)는 재귀적 구조이다.

"적을 발견했나?" → "공격 가능한 거리인가?" → "어떤 공격을 쓸까?"
이런 의사 결정이 트리 구조로 이루어 지며, 트리 탐색은 본질적으로 재귀.

 - UE5 행동 트리: 내부적으로 재귀 탐색

 - 프랙탈 지형 생성: 재귀로 지형을 세분화

 - 파티클 시스템: 분기 구조

웹/서버

JSON 파싱이 대표적인 재귀 활용이다.

{"user": {"address": {"city": {"name": "Seoul" }}}}

객체 안에 객체, 그 안에 또 객체... 중첩 구조를 다루려면 재귀가 자연스럽다.

 - 파일 시스템 탐색: 폴더 안에 폴더 안에 폴더...

 - DOM 트리 순회: HTML 요소 안에 요소...

CS 전반

재귀는 컴퓨터 과학의 심장과도 같다.

수학적 귀납법과 같은 원리
 : "작은 경우에서 성립하면 큰 경우에도 성립"
 → 알고리즘의 정확성 증명에 사용

 - 함수형 언어(Haskell, Lisp): 반복문 대신 재귀가 기본

 - 컴파일러: 재귀적 하강 파서(Recursive Descent Parser)

 - 프로그래머스 Level 5: 그래프/트리 탐색(DFS)에서 재귀가 다시 주인공

"자기 자신을 참조하는 구조"는 CS의 가장 근본적인 패턴이다.

---

오늘의 핵심

재귀 = 자기 자신을 호출하는 함수
 - 핵심 두 요소: 재귀 호출 + 종료 조건(base case)

재귀는 콜 스택을 사용한다.
 - 호출할 때마다 스택 프레임이 쌓이고, base case에서 돌아오며 빠진다.

종료 조건을 빼먹으면 스택 오버플로우
 - 무한 호출 → 메모리 초과 → 크래시. "base case를 먼저 쓰자!"

재귀적 사고 = "작은 문제로 바꾸기"
 - 팩토리얼, 피보나치, 문자열 뒤집기, 거듭제곱 → 모두 "전체 = 작은 부분 + 나머지"

재귀 vs 반복문은 도구 선택
 - 구조가 재귀적이면 재귀, 단순 반복이면 for문