--- title: "부른 순서대로 쌓이고 반대로 풀린다" description: "메서드가 자기를 부르면 호출이 겹겹이 쌓입니다. 쌓이는 자리에는 한계가 있고, 짧은 코드가 빠른 코드는 아닙니다." author: "유니얼" pubDate: 2026-09-08 category: "programming/csharp/basics" tags: ["C#", "기초"] canonical: https://blog.unialgames.com/posts/csharp-recursion/ --- 메서드 안에서 다른 메서드를 부를 수 있습니다. 그럼 자기 자신을 불러도 될까요. 됩니다. ```csharp int Factorial(int n) { if (n <= 1) { return 1; } return n * Factorial(n - 1); } ``` `5!` 는 `5 × 4!` 이고, `4!` 는 `4 × 3!` 입니다. **큰 문제를 한 단계 작은 같은 문제로 바꾸는 것**, 이게 재귀입니다. > **재귀에는 두 부분이 있습니다. 한 단계 줄이는 식과, 더 줄일 수 없는 지점입니다.** ## 종료 조건이 없으면 죽는다 더 줄일 수 없는 지점을 종료 조건이라고 합니다. 위 코드에서는 `n <= 1` 입니다. 이게 없으면 어떻게 될까요. ```csharp int Factorial(int n) { return n * Factorial(n - 1); // 종료 조건이 없습니다 } ``` `5` 는 `4` 를 부르고, `4` 는 `3` 을, `3` 은 `2` 를, `1` 은 `0` 을, `0` 은 `-1` 을 부릅니다. 끝나지 않습니다. 앞에서 본 무한 루프와 같은 실수인데 **결과가 다릅니다.** 무한 루프는 프로그램이 계속 돌기만 하고, 이건 `StackOverflowException` 으로 **죽습니다.** 왜 죽는지 보려면 호출이 어떻게 쌓이는지를 봐야 합니다. ## 호출은 쌓였다가 반대로 풀린다 앞에서 메서드를 부르면 돌아올 자리를 어딘가에 쌓아 둔다고 했습니다. 그 어딘가가 스택입니다. 나중에 넣은 것이 먼저 나오는 그 스택 맞습니다. 내려갈 때는 **계산이 안 끝난 자리가 쌓입니다.** `Factorial(3)` 은 `3 × ?` 까지 적어 두고 멈춰 있습니다. `?` 를 알아야 끝납니다. 올라올 때 그 `?` 가 하나씩 채워집니다. 가장 나중에 쌓인 것부터 풀립니다. 종료 조건이 없으면 **내려가기만 하고 올라오지 않습니다.** 쌓이는 자리는 무한하지 않습니다. 한계에 닿으면 `StackOverflowException` 입니다. 보통 수천에서 수만 번 깊이에서 터집니다. ## 반복문으로도 되는데 왜 `Factorial` 은 반복문으로도 씁니다. ```csharp int Factorial(int n) { int result = 1; for (int i = 2; i <= n; i++) { result *= i; } return result; } ``` 이쪽이 더 낫습니다. 쌓이는 것이 없고, 깊이 걱정도 없습니다. **단순히 줄어드는 문제는 반복문이 낫습니다.** 재귀가 어울리는 것은 갈래가 여럿으로 뻗는 구조입니다. 폴더 안에 폴더가 있고 그 안에 또 폴더가 있는 것, 트리 모양의 데이터 같은 것들입니다. 그런 걸 반복문으로 쓰려면 결국 스택을 직접 만들어서 쌓아야 합니다. 그럴 거면 이미 있는 호출 스택을 쓰는 편이 짧고 읽힙니다. ## 짧은 코드가 빠른 코드는 아니다 재귀의 진짜 함정은 깊이가 아니라 **중복 계산**입니다. 피보나치가 유명한 예입니다. ```csharp int Fib(int n) { if (n <= 1) return n; return Fib(n - 1) + Fib(n - 2); } ``` 세 줄입니다. 문제 정의를 그대로 옮겨 적은 것처럼 깔끔합니다. 그런데 `Fib(5)` 를 부르면 무슨 일이 일어나는지 보면 이렇습니다. `Fib(5)` 는 `Fib(4)` 와 `Fib(3)` 을 부릅니다. `Fib(4)` 는 다시 `Fib(3)` 과 `Fib(2)` 를 부릅니다. **`Fib(3)` 을 두 번 계산합니다.** 그리고 그 안에서 `Fib(2)` 를 또 여러 번 계산합니다. `n` 을 40 으로 올려 보세요. 재귀 쪽은 수억 번입니다. 반복문으로 쓰면 40 번입니다. **코드가 짧다고 빠른 것은 아닙니다.** 이 경우는 짧아서 오히려 감춰집니다. 세 줄짜리 코드가 수억 번을 도는 것이 눈에 안 보입니다. 이미 계산한 값을 어딘가에 저장해 두고 다시 쓰면 이 문제는 사라집니다. `Dictionary` 가 그런 저장에 어울립니다. 이렇게 계산 결과를 기억해 두는 방식을 메모이제이션이라고 부릅니다. ## 재귀를 쓸 때 확인할 것 반복문에서 "무엇이 이 조건을 거짓으로 만드는가" 를 확인했습니다. 재귀에서는 세 가지입니다. - **종료 조건이 있는가.** 없으면 죽습니다. - **매번 그 조건에 가까워지는가.** `Factorial(n - 1)` 처럼 줄어들어야 합니다. `Factorial(n)` 을 다시 부르면 종료 조건이 있어도 못 만납니다. - **얼마나 깊어지는가.** 수만 번 깊어질 수 있으면 반복문으로 바꿉니다. ## 정리 - 재귀는 큰 문제를 한 단계 작은 같은 문제로 바꾸는 것입니다. - 더 줄일 수 없는 지점이 종료 조건입니다. 없으면 `StackOverflowException` 으로 죽습니다. - 호출할 때마다 자리가 쌓이고, 값을 돌려줄 때 반대 순서로 풀립니다. - 쌓이는 자리에는 한계가 있습니다. 무한 루프와 달리 프로그램이 죽습니다. - 단순히 줄어드는 문제는 반복문이 낫습니다. 재귀는 갈래가 뻗는 구조에 어울립니다. - 피보나치처럼 같은 값을 다시 계산하는 재귀는 짧지만 아주 느립니다. - 종료 조건이 있는가, 매번 가까워지는가, 얼마나 깊어지는가를 확인합니다.