이 글에서는 재귀(recursion)를 활용하여 N개 숫자의 합을 구하는 Java 프로그램을 살펴봅니다. 재귀 함수란 특정 조건이 만족될 때까지 스스로를 반복해서 호출하는 함수를 의미합니다.
재귀(Recursion)란 무엇인가?
재귀는 자기 유사(self-similar)한 방식으로 동일한 작업을 반복하는 프로세스입니다. 프로그래밍 언어에서 하나의 함수가 자기 자신을 다시 호출할 수 있다면, 이를 그 함수의 재귀 호출이라고 부릅니다.
대부분의 프로그래밍 언어는 스택(stack)을 사용해 재귀를 구현합니다. 일반적으로 함수(호출자)가 다른 함수 또는 자기 자신(피호출자)을 호출하면, 호출자는 실행 제어권을 피호출자에게 넘기게 됩니다. 이 과정에서 호출자와 피호출자 사이에 데이터가 전달되기도 합니다.
실행 결과 미리보기
입력 예시
N 값 입력 : 6 배열 요소 입력 : 15 30 45 80 100 140
출력 예시
N개 숫자의 총합은 : 410
알고리즘
1단계 - 시작
2단계 - 정수형 변수 N, my_sum, i와 정수 배열 'my_array' 선언
3단계 - 사용자로부터 필요한 값을 입력받거나 직접 값을 정의
4단계 - 두 개의 정수를 매개변수로 받는 재귀 함수 'RecursiveSum' 정의.
이 함수는 기저 조건(base condition)에 도달할 때까지
스스로를 반복 호출하며 합계를 계산합니다.
5단계 - 재귀 함수 'RecursiveSum'을 호출하고 결과값 저장
6단계 - 결과 출력
7단계 - 종료예제 1: 사용자 입력으로 합계 구하기
아래 예제는 사용자로부터 N과 배열 요소를 직접 입력받아 재귀 함수로 합계를 계산합니다.
import java.util.Scanner;
public class ArraySum {
public static int RecursiveSum(int my_array[], int i, int N){
if (i == N)
return 0;
return my_array[i] + RecursiveSum(my_array, i + 1, N);
}
public static void main(String[] args){
int N, my_sum, i;
my_sum = 0;
System.out.println("필요한 패키지가 임포트되었습니다");
Scanner my_scanner = new Scanner(System.in);
System.out.println("Scanner 객체가 생성되었습니다");
System.out.print("N 값 입력 : ");
N = my_scanner.nextInt();
int my_array[] = new int[N];
System.out.println("배열의 요소들을 입력하세요 :");
for (i = 0; i < N; i++) {
my_array[i] = my_scanner.nextInt();
}
my_sum = RecursiveSum(my_array, 0, N);
System.out.println("\nN개 숫자의 총합은 : " + my_sum);
}
}실행 결과
필요한 패키지가 임포트되었습니다 Scanner 객체가 생성되었습니다 N 값 입력 : 6 배열의 요소들을 입력하세요 : 15 30 45 80 100 140 N개 숫자의 총합은 : 410
예제 2: 미리 정의된 배열로 합계 구하기
아래 예제는 배열과 크기를 코드 내에서 미리 정의하고, 같은 재귀 방식으로 합계를 계산해 콘솔에 출력합니다.
public class Main {
public static int RecursiveSum(int[] my_array, int i, int N){
if (i == N)
return 0;
return my_array[i] + RecursiveSum(my_array, i + 1, N);
}
public static void main(String[] args) {
int[] my_array = {15, 30, 45, 80, 100, 140};
int array_size = my_array.length;
System.out.println("배열의 요소들은 다음과 같이 정의되어 있습니다 :");
for (int i = 0; i < array_size; i++) {
System.out.print(my_array[i] + " ");
}
int my_sum = RecursiveSum(my_array, 0, array_size);
System.out.println("\nN개 숫자의 총합은 : " + my_sum);
}
}실행 결과
배열의 요소들은 다음과 같이 정의되어 있습니다 : 15 30 45 80 100 140 N개 숫자의 총합은 : 410
재귀 함수의 동작 원리
RecursiveSum 함수의 핵심 로직은 다음과 같습니다.
- 기저 조건(Base Case): 인덱스
i가N에 도달하면 0을 반환하며 재귀 호출을 종료합니다. - 재귀 단계(Recursive Step): 현재 인덱스의 배열 요소에 나머지 요소들의 합(
RecursiveSum(my_array, i+1, N))을 더해 반환합니다.
이처럼 각 호출이 스택에 쌓인 뒤 기저 조건에서부터 차례로 거슬러 올라가며 합산되므로, 반복문 없이도 배열 전체의 합을 손쉽게 구할 수 있습니다. 다만 깊은 재귀 호출 시 StackOverflowError가 발생할 수 있으므로, 배열 크기가 매우 클 경우에는 반복문 방식이나 꼬리 재귀 최적화를 고려하는 것이 좋습니다.