6주차

Recursion

개념

Recursion(재귀) 란?

함수가 자기 자신을 다시 호출하는 방식입니다

n! = n * (n - 1)!
하노이의 탑
트리 탐색
DFS
순열 / 조합
백트래킹
분할 정복 같은 문제들이 재귀로 표현 가능합니다

즉, 재귀는 단순히 “함수가 자기 자신을 부른다”가 아니라 [지금 문제를 해결하려면, 크기가 더 작은 같은 문제를 먼저 해결하면 된다] 같이 바라보는 방식입니다.

재귀 함수의 기본 구조는 보통 다음과 같습니다.

voidrecursive(intn) {
if (n==0) {
return;
    }

recursive(n-1);
}

재귀 함수에서 가장 중요한 요소는 3가지입니다.

요소	의미	예시
종료 조건	재귀 호출을 멈추는 조건	if (n == 0) return;
재귀 호출	자기 자신을 다시 호출	recursive(n - 1);
상태 변화	종료 조건에 가까워지도록 값이 변함	n이 1씩 감소

이 3가지 중 하나라도 빠지면 재귀는 제대로 동작하지 않습니다.

특히 종료 조건이 없거나, 재귀 호출을 해도 값이 변하지 않으면 무한 재귀가 발생합니다.

재귀 함수의 작동 방식

재귀 함수는 호출될 때마다 메모리의 호출 스택(Call Stack) 에 쌓입니다.

예를 들어 다음 코드가 있다고 해보면,

voidrecursive(intn) {
if (n==0) {
return;
    }
System.out.println("호출 전: "+n);
recursive(n-1);
System.out.println("호출 후: "+n);
}

recursive(3)을 호출했을 때 흐름은 다음과 같습니다.

recursive(3)
  recursive(2)
    recursive(1)
      recursive(0)

함수는 호출될 때는 아래로 계속 들어가고, 종료될 때는 거꾸로 돌아옵니다.

따라서 출력 순서는 다음과 비슷하게 나옵니다.

호출 전: 3
호출 전: 2
호출 전: 1
호출 후: 1
호출 후: 2
호출 후: 3

여기서 중요한 점은 다음입니다.

재귀 호출 전에 있는 코드는 내려가면서 실행됩니다.

재귀 호출 후에 있는 코드는 모든 재귀 호출이 끝난 뒤, 돌아오면서 실행됩니다.

이 감각이 있어야 DFS, 백트래킹, 하노이의 탑 문제를 이해하기 쉽습니다.

재귀와 반복문의 관계

많은 재귀 코드는 반복문으로도 바꿀 수 있습니다.

예를 들어 1부터 N까지 출력하는 문제는 재귀보다 반복문이 더 간단합니다.

for (inti=1;i<=n;i++) {
System.out.println(i);
}

하지만 다음과 같은 구조에서는 재귀가 훨씬 자연스럽습니다.

트리처럼 깊이가 있는 구조
그래프 탐색
하노이의 탑
순열 / 조합
백트래킹
분할 정복

정리하면, 단순 반복은 반복문이 유리하고, 문제가 여러 단계로 깊게 들어가는 구조라면 재귀가 유리합니다.

구분	반복문	재귀
방식	같은 작업을 반복	자기 자신을 호출
장점	메모리 사용이 적고 빠른 편	문제 구조를 직관적으로 표현 가능
단점	복잡한 구조에서는 코드가 길어질 수 있음	호출 스택이 깊어지면 위험
자주 쓰는 곳	단순 순회, 누적합	DFS, 백트래킹, 트리, 분할 정복

재귀 트리란?

재귀 트리는 재귀 함수가 호출되는 흐름을 트리 형태로 표현한 것입니다.

예를 들어 피보나치 수를 재귀로 구하면 다음과 같은 구조가 됩니다.

fib(5)
├── fib(4)
│   ├── fib(3)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

이렇게 재귀 호출이 여러 갈래로 나뉘는 경우, 호출 흐름을 트리처럼 생각하면 이해하기 쉽습니다.

다만 피보나치처럼 같은 값이 반복해서 호출되는 재귀는 비효율적일 수 있습니다.

예를 들어 fib(5)를 구할 때 fib(3), fib(2)가 여러 번 반복 계산됩니다.

이런 경우에는 단순 재귀보다 메모이제이션이나 동적 프로그래밍(DP) 을 함께 사용하는 것이 좋습니다.

문제 패턴

패턴 1. 단순 재귀

가장 기본적인 재귀 문제입니다.

문제 예시 형태

1부터 N까지 출력하기
N부터 1까지 출력하기
팩토리얼 구하기
자릿수 합 구하기
문자열 뒤집기

핵심 포인트

종료 조건을 먼저 작성해야 함
매개변수가 종료 조건에 가까워져야 함
재귀 호출 전후 코드의 실행 순서를 구분해야 함

예를 들어 팩토리얼은 다음처럼 생각할 수 있습니다.

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)

종료 조건은 factorial(1) = 1입니다.

패턴 2. 분할 정복

큰 문제를 작은 문제로 나누어 해결하는 방식입니다.

문제 예시 형태

병합 정렬
퀵 정렬
이진 탐색
거듭제곱 구하기
큰 배열을 반으로 나누어 처리하기

핵심 포인트

문제를 더 작은 문제로 나눈다.
작은 문제의 결과를 합쳐서 전체 문제를 해결한다.
보통 start, end, mid 같은 범위 인덱스를 많이 사용한다.

분할 정복은 보통 다음 흐름을 가집니다.

문제 나누기
→ 작은 문제 해결하기
→ 결과 합치기

패턴 3. DFS / 트리 탐색

재귀가 가장 많이 사용되는 대표적인 패턴입니다.

문제 예시 형태

그래프에서 연결된 노드 탐색
트리의 전위 / 중위 / 후위 순회
미로 탐색
깊이 우선 탐색
모든 경로 탐색

핵심 포인트

현재 위치에서 갈 수 있는 다음 위치를 재귀 호출한다.
이미 방문한 곳을 다시 방문하지 않도록 처리해야 한다.
그래프에서는 visited 배열이 자주 필요하다.

기본 구조는 다음과 비슷합니다.

voiddfs(intnode) {
visited[node]=true;

for (intnext :graph[node]) {
if (!visited[next]) {
dfs(next);
        }
    }
}

DFS는 현재 노드에서 최대한 깊게 들어간 뒤, 더 이상 갈 곳이 없으면 되돌아오는 방식입니다.

패턴 4. 백트래킹

백트래킹은 재귀를 이용해 가능한 경우를 탐색하되, 조건에 맞지 않으면 되돌아가는 방식입니다.

문제 예시 형태

순열 만들기
조합 만들기
N-Queen
부분집합 만들기
암호 만들기
가능한 모든 경우 탐색

핵심 포인트

선택한다.
재귀 호출한다.
선택을 취소한다.

이 흐름이 가장 중요합니다.

선택
→ 재귀 호출
→ 선택 취소

예를 들어 순열을 만들 때는 하나의 숫자를 선택하고, 다음 자리로 들어간 뒤, 다시 돌아와서 선택을 취소해야 합니다.

selected[i]=true;
dfs(depth+1);
selected[i]=false;

여기서 마지막 줄의 선택 취소를 빼먹으면 다음 경우의 수를 제대로 탐색할 수 없습니다.

패턴 5. 하노이의 탑

재귀 구조를 이해하기에 가장 대표적인 문제입니다.

문제 예시 형태

N개의 원판을 1번 기둥에서 3번 기둥으로 옮기기
한 번에 하나의 원판만 옮길 수 있음
큰 원판은 작은 원판 위에 올릴 수 없음
이동 과정을 출력하거나 배열로 반환해야 함

핵심 포인트

N개의 원판을 옮기는 문제는 다음 3단계로 나눌 수 있습니다.

1. 위의 N - 1개 원판을 보조 기둥으로 옮긴다.
2. 가장 큰 원판을 목표 기둥으로 옮긴다.
3. 보조 기둥에 있던 N - 1개 원판을 목표 기둥으로 옮긴다.

즉, 하노이의 탑은 다음 구조를 가집니다.

hanoi(n, from, to, via)
n개의 원판을 from에서 to로 옮긴다.
via는 보조 기둥이다.

이 문제는 재귀 호출의 순서가 매우 중요합니다.

예시 문제 기반 설명

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스 기준으로는 하노이의 탑 문제가 대표적인 재귀 문제입니다.

풀이 방법

이 문제의 핵심은 “N개의 원판을 한 번에 옮긴다”라고 생각하지 않는 것입니다.

대신 다음처럼 생각해야 합니다.

N개의 원판을 1번 기둥에서 3번 기둥으로 옮기려면,

1. N - 1개의 원판을 1번 기둥에서 2번 기둥으로 옮긴다.
2. 가장 큰 원판을 1번 기둥에서 3번 기둥으로 옮긴다.
3. N - 1개의 원판을 2번 기둥에서 3번 기둥으로 옮긴다.

이때 N - 1개의 원판을 옮긴다는 작업도 똑같은 하노이 문제입니다.

그래서 재귀로 해결할 수 있습니다.

함수 정의를 먼저 정하면 다음과 같습니다.

hanoi(n, from, to, via)

n개의 원판을 from 기둥에서 to 기둥으로 옮긴다.
via는 보조 기둥이다.

종료 조건은 원판이 1개일 때입니다.

원판이 1개라면 그냥 from에서 to로 옮기면 된다.

전체 흐름은 다음과 같습니다.

hanoi(n - 1, from, via, to)
from → to 이동
hanoi(n - 1, via, to, from)

이 문제의 이동 횟수는 2^N - 1번입니다.

따라서 시간복잡도는 O(2^N)이고, 재귀 깊이는 O(N)입니다.

Java

import java.util.*;

class Solution {
    public int[][] solution(int n) {
        List<int[]> moves = new ArrayList<>();

        hanoi(n, 1, 3, 2, moves);

        int[][] answer = new int[moves.size()][2];

        for (int i = 0; i < moves.size(); i++) {
            answer[i] = moves.get(i);
        }

        return answer;
    }

    private void hanoi(int n, int from, int to, int via, List<int[]> moves) {
        // 종료 조건: 원판이 1개라면 바로 이동
        if (n == 1) {
            moves.add(new int[]{from, to});
            return;
        }

        // 1. 위의 n - 1개 원판을 보조 기둥으로 이동
        hanoi(n - 1, from, via, to, moves);

        // 2. 가장 큰 원판을 목표 기둥으로 이동
        moves.add(new int[]{from, to});

        // 3. 보조 기둥에 있던 n - 1개 원판을 목표 기둥으로 이동
        hanoi(n - 1, via, to, from, moves);
    }
}

Python

def solution(n):
    answer = []

    def hanoi(n, from_pole, to_pole, via_pole):
        # 종료 조건: 원판이 1개라면 바로 이동
        if n == 1:
            answer.append([from_pole, to_pole])
            return

        # 1. 위의 n - 1개 원판을 보조 기둥으로 이동
        hanoi(n - 1, from_pole, via_pole, to_pole)

        # 2. 가장 큰 원판을 목표 기둥으로 이동
        answer.append([from_pole, to_pole])

        # 3. 보조 기둥에 있던 n - 1개 원판을 목표 기둥으로 이동
        hanoi(n - 1, via_pole, to_pole, from_pole)

    hanoi(n, 1, 3, 2)

    return answer

JavaScript

function solution(n) {
  const answer = [];

  function hanoi(n, from, to, via) {
    // 종료 조건: 원판이 1개라면 바로 이동
    if (n === 1) {
      answer.push([from, to]);
      return;
    }

    // 1. 위의 n - 1개 원판을 보조 기둥으로 이동
    hanoi(n - 1, from, via, to);

    // 2. 가장 큰 원판을 목표 기둥으로 이동
    answer.push([from, to]);

    // 3. 보조 기둥에 있던 n - 1개 원판을 목표 기둥으로 이동
    hanoi(n - 1, via, to, from);
  }

  hanoi(n, 1, 3, 2);

  return answer;
}

실수 포인트

재귀 문제에서 가장 흔한 실수는 종료 조건을 빼먹는 것입니다.

종료 조건이 없으면 함수가 계속 자기 자신을 호출하게 되고, 결국 호출 스택이 가득 차서 오류가 발생합니다.

Java에서는 StackOverflowError, Python에서는 RecursionError, JavaScript에서는 Maximum call stack size exceeded 같은 오류가 발생할 수 있습니다.

하노이의 탑 문제에서는 매개변수 순서를 헷갈리지 않아야 합니다.

hanoi(n, from, to, via)

이 함수는 n개의 원판을 from에서 to로 옮기고, via를 보조 기둥으로 사용한다는 뜻입니다.

재귀 호출 순서는 다음 구조를 기억하면 됩니다.

hanoi(n - 1, from, via, to)
from → to
hanoi(n - 1, via, to, from)

즉, 위의 n - 1개를 보조 기둥으로 옮기고, 가장 큰 원판을 목표 기둥으로 옮긴 뒤, 다시 n - 1개를 목표 기둥으로 옮기는 방식입니다.

또한 종료 조건도 반드시 필요합니다.

if (n==1) {
moves.add(newint[]{from,to});
return;
}

종료 조건이 없으면 재귀 호출이 끝나지 않아 스택 오버플로우가 발생할 수 있습니다.

재귀 문제를 풀 때는 다음 순서로 접근하면 좋습니다.

1. 이 함수가 무슨 일을 하는지 한 문장으로 정의한다.
2. 가장 작은 문제, 즉 종료 조건을 정한다.
3. 큰 문제를 작은 문제로 어떻게 줄일지 정한다.
4. 재귀 호출 전후에 어떤 작업을 해야 하는지 확인한다.
5. 상태 복구가 필요한 문제인지 확인한다.

🏠 메인

Home

📖 기본 코테 개념

Time Complexity

Space Complexity

Big-O Notation

Input Size & Algorithm Complexity

📅 주차별 개념

👥 담당 순서

백현빈 → 강민주 → 조수빈 → 임현빈 → 전병훈 → 이건희

(이후 동일한 순서로 반복)

Uh oh!

6주차

Recursion

개념

재귀 함수의 작동 방식

재귀와 반복문의 관계

재귀 트리란?

문제 패턴

패턴 1. 단순 재귀

패턴 2. 분할 정복

패턴 3. DFS / 트리 탐색

패턴 4. 백트래킹

패턴 5. 하노이의 탑

예시 문제 기반 설명

문제

풀이 방법

Java

Python

JavaScript

실수 포인트

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

🏠 메인

📖 기본 코테 개념

📅 주차별 개념

1 ~ 5주차

6 ~ 10주차

11 ~ 15주차

👥 담당 순서

Clone this wiki locally