1. 순환(재귀, Recursion)이란?
순환은 알고리즘이나 함수가 자기 자신을 다시 호출하는 기법이다.
쉽게 말해, “큰 문제를 작은 문제로 쪼개서, 그 작은 문제를 자기 자신이 다시 해결하도록 하는 방식”이다.
예를 들어,
“1부터 n까지 곱하라” → “n × (1부터 n-1까지 곱한 결과)”
이렇게 문제를 더 작은 버전으로 줄이는 게 순환의 핵심 구조다.
모든 순환은 반복문(while, for)으로 바꿀 수 있지만, 문제의 구조가 자연스럽게 분할되는 경우, 순환이 훨씬 이해하기 쉽고 코드도 깔끔하다.
2. 팩토리얼(Factorial)
팩토리얼은 1부터 n까지의 모든 자연수를 곱한 값이다.
n! = n × (n - 1) × (n - 2) × ... × 1
💡 순환 정의
factorial(n) = 1, if n == 0 or n == 1
factorial(n) = n × factorial(n - 1), if n > 1💻 C 예제
int factorial(int n) {
if (n <= 1) return 1;
else return n * factorial(n - 1);
}이 함수는 n이 1이 될 때까지 자기 자신을 계속 호출하며,
“문제를 점점 작게 만들다가” 마지막에 한 번에 결과를 계산해 반환한다.
⚙️ 작동 예시
factorial(4) → 4 × factorial(3) → 4 × 3 × factorial(2) → 4 × 3 × 2 × factorial(1) → 4 × 3 × 2 × 1
즉, 24가 된다.
3. 피보나치 수열(Fibonacci)
피보나치 수열은 앞의 두 항을 더해서 다음 항을 만드는 수열이다.
0, 1, 1, 2, 3, 5, 8, 13, 21...
💡 순환 정의
fibonacci(n) = 0, if n == 0
fibonacci(n) = 1, if n == 1
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2), if n >= 2💻 C 예제
int factorial(int n) {
if (n <= 1) return 1;
else return n * factorial(n - 1);
}⚠️ 비효율성의 이유
이 방식은 간단하지만, 같은 값을 여러 번 계산한다.
예를 들어 fibonacci(5)를 구할 때, fibonacci(3)을 두 번 이상 호출한다.
즉, 중복 호출로 인해 시간이 기하급수적으로 증가(O(2ⁿ)) 한다.
이런 문제는 반복문이나 메모이제이션(Memoization) 으로 개선할 수 있다.
4. 하노이탑(Hanoi Tower)
하노이탑은 “원판을 다른 기둥으로 옮기되, 한 번에 한 개씩, 큰 원판은 작은 원판 위에 올릴 수 없다”는 규칙의 문제다.
이건 순환(재귀)으로만 효율적으로 풀 수 있다.
💡 순환 정의
move(n, from, to, via)
1. if n == 1 → from에서 to로 원판 이동
2. else
- move(n-1, from, via, to)
- from에서 to로 원판 이동
- move(n-1, via, to, from)💻 C 예제
void hanoi(int n, char from, char to, char via) {
if (n == 1) printf("%c → %c\n", from, to);
else {
hanoi(n - 1, from, via, to);
printf("%c → %c\n", from, to);
hanoi(n - 1, via, to, from);
}
}⚙️ 동작 원리
3개의 원판을 A에서 C로 옮긴다고 하면,
- 작은 두 개를 B로 옮긴다.
- 가장 큰 원판을 C로 옮긴다.
- B에 있던 두 개를 다시 C로 옮긴다.
즉, 문제를 절반으로 줄이고, 같은 방법으로 다시 해결하는 구조이다.
이것이 순환의 본질적 사고 방식이다.
📘 정리하자면
- 팩토리얼 → 순환이 가장 자연스러운 예.
- 피보나치 → 구조는 단순하지만 성능은 나쁨.
- 하노이탑 → 순환의 개념을 가장 완벽히 보여주는 대표 문제.
이 세 가지를 이해하면 순환(recursion) 개념을 완전히 잡을 수 있다.
순환은 단순 반복이 아니라 “문제를 자기 자신으로 줄이는 사고 방식” 이다.
🔑 단어정리
순환(循環)
- 한자: 돌 순(循), 돌 고리 환(環) → ‘빙 돌아 되풀이함’
- 영어: Recursion (re- ‘다시’ + currere ‘달리다’) → ‘다시 달리다, 자기 자신으로 돌아가다’
팩토리얼(階乘)
- 한자: 층 계(階), 탈 승(乘) → ‘단계를 밟아 곱함’
- 영어: Factorial (factor ‘곱하는 수’ + -al ‘형용사형 어미’)
피보나치 수열(Fibonacci sequence)
- 피보나치(Fibonacci): 이탈리아 수학자 이름에서 유래
- Sequence (sequi, ‘따르다’) → ‘따라 이어지는 것’
하노이탑(河內塔)
- 한자: 강 이름 하(河), 안 내(內), 탑 탑(塔) → ‘하노이의 탑’ (베트남 하노이 전설에서 유래)
- 영어: Tower of Hanoi