재귀(Recursion)와 반복(Iteration)은 모두 일련의 명령문을 반복적으로 실행한다는 공통점이 있습니다. 재귀는 함수 내부의 문장이 자기 자신을 계속 호출하는 방식이고, 반복은 루프가 제어 조건이 거짓(false)이 될 때까지 계속 실행되는 방식입니다. 두 방식의 핵심적인 차이는 재귀가 항상 함수에 적용되는 프로세스라는 점이며, 반복은 반복적으로 실행하고자 하는 명령문 집합에 적용된다는 점입니다.
재귀(Recursion)란?
- 재귀는 선택(selection) 구조를 사용합니다.
- 재귀 단계가 특정 조건(기저 사례, base case)으로 수렴하는 방식으로 문제를 줄이지 못하면 무한 재귀가 발생하며, 이는 시스템 전체를 다운시킬 수 있습니다.
- 재귀는 기저 사례(base case)가 인식되는 시점에 종료됩니다.
- 스택을 유지 관리해야 하는 오버헤드 때문에 재귀는 일반적으로 반복보다 느립니다.
- 재귀는 반복보다 더 많은 메모리를 사용합니다.
- 재귀를 사용하면 코드가 더 간결해집니다.
재귀 예제
public class RecursionExample {
public static void main(String args[]) {
RecursionExample re = new RecursionExample();
int result = re.factorial(4);
System.out.println("Result:" + result);
}
public int factorial(int n) {
if (n==0) {
return 1;
}
else {
return n*factorial(n-1);
}
}
}
실행 결과
Result:24
위 예제는 팩토리얼을 계산하는 대표적인 재귀 코드입니다. factorial 메서드가 자기 자신을 호출하며 n이 0이 될 때까지 문제를 점차 줄여나가고, n이 0인 기저 사례에 도달하면 재귀 호출이 종료됩니다.
반복(Iteration)이란?
- 반복은 반복(repetition) 구조를 사용합니다.
- 루프 조건 검사가 거짓이 되지 않으면 무한 루프가 발생하며, 무한 루프는 CPU 사이클을 지속적으로 소모합니다.
- 반복은 루프 조건이 실패(거짓)하는 시점에 종료됩니다.
- 반복은 스택을 사용하지 않기 때문에 재귀보다 빠릅니다.
- 반복은 메모리를 적게 소비합니다.
- 반복을 사용하면 코드가 더 길어지는 경향이 있습니다.
반복 예제
public class IterationExample {
public static void main(String args[]) {
for(int i = 1; i <= 5; i++) {
System.out.println(i + " ");
}
}
}
실행 결과
1 2 3 4 5
위 예제는 for 루프를 사용해 1부터 5까지 숫자를 출력하는 기본적인 반복 코드입니다. 조건식 i <= 5가 거짓이 되는 순간 루프가 종료됩니다.
정리: 재귀 vs 반복 비교
재귀는 코드가 간결하고 복잡한 문제(예: 트리 순회, 분할 정복)를 직관적으로 표현할 수 있다는 장점이 있지만, 스택 오버헤드로 인해 속도와 메모리 측면에서 불리합니다. 반대로 반복은 성능과 메모리 효율이 뛰어나지만 코드가 길어질 수 있습니다. 따라서 문제의 성격과 성능 요구 사항에 따라 적절한 방식을 선택하는 것이 중요합니다.