재귀 함수를 이용해 자연수의 합을 구하는 Java 프로그램

이 글에서는 재귀(recursion)를 사용하여 자연수의 합을 구하는 방법을 살펴봅니다. 자연수란 1부터 무한대까지의 모든 양의 정수를 의미하며, 재귀 함수란 특정 조건이 만족될 때까지 스스로를 반복적으로 호출하는 함수를 말합니다.

재귀는 항목들을 자기 유사적(self-similar) 방식으로 반복하는 과정입니다. 프로그래밍 언어에서 하나의 함수가 같은 함수 내부에서 자기 자신을 호출할 수 있을 때, 이를 함수의 재귀 호출(recursive call)이라고 합니다.

많은 프로그래밍 언어는 스택(stack)을 이용해 재귀를 구현합니다. 일반적으로 어떤 함수(호출자)가 다른 함수(피호출자) 또는 자기 자신을 호출하면, 호출자는 실행 제어권을 피호출자에게 넘기며, 이 과정에서 데이터도 함께 전달될 수 있습니다.

재귀 호출의 흐름을 간단히 표현하면 다음과 같습니다. 예를 들어 Add(25)는 25 + Add(24) → 24 + Add(23) → … → Add(1) → Add(0) 순으로 호출되며, 입력값이 0에 도달하면 더 이상 자기 자신을 호출하지 않고 0을 반환합니다. 이후 호출이 거슬러 올라가면서 모든 값이 더해져 최종 합계 325가 계산됩니다.

다음은 입출력 예시입니다.

입력

사용자가 아래와 같이 입력했다고 가정해 보겠습니다.

숫자 입력 : 25

출력

실행 결과는 다음과 같습니다.

25까지의 자연수의 합은 325입니다

알고리즘

1단계 - 시작한다.
2단계 - my_input, my_sum 두 개의 정수 변수를 선언한다.
3단계 - 사용자로부터 필요한 값을 입력받거나 값을 미리 정의한다.
4단계 - 정수를 매개변수로 받아, 입력값이 0이 될 때까지 현재 값과 그보다 1 작은 값의 재귀 호출 결과를 더해 반환하는 재귀 함수 'Add'를 정의한다.
5단계 - 재귀 함수를 호출하면서 'my_input' 값을 전달하고, 반환값을 저장한다.
6단계 - 결과를 화면에 출력한다.
7단계 - 종료한다.

예제 1: 사용자 입력값 사용

이 예제에서는 Scanner를 통해 사용자가 직접 숫자를 입력하는 방식을 사용합니다.

import java.util.Scanner;
public class NaturalNumbers {
    public static void main(String[] args) {
        int my_input, my_sum;
        System.out.println("필요한 패키지를 가져왔습니다");
        Scanner my_scanner = new Scanner(System.in);
        System.out.println("리더(reader) 객체가 정의되었습니다");
        System.out.print("숫자를 입력하세요 : ");
        my_input = my_scanner.nextInt();
        System.out.println("입력된 숫자는 " + my_input + "입니다");
        my_sum = Add(my_input);
        System.out.println(my_input + "까지의 자연수의 합은 " + my_sum + "입니다");
    }
    public static int Add(int my_input) {
        if (my_input > 0)
            return my_input + Add(my_input - 1);
        else
            return my_input;
    }
}

출력

필요한 패키지를 가져왔습니다
리더(reader) 객체가 정의되었습니다
숫자를 입력하세요 : 25
입력된 숫자는 25입니다
25까지의 자연수의 합은 325입니다

예제 2: 미리 정의된 값 사용

이 예제에서는 정수값이 코드 안에 미리 정의되어 있으며, 해당 값을 콘솔에 바로 출력합니다.

public class NaturalNumbers {
    public static void main(String[] args) {
        int my_input, my_sum;
        my_input = 25;
        System.out.println("정의된 숫자는 " + my_input + "입니다");
        my_sum = Add(my_input);
        System.out.println(my_input + "까지의 자연수의 합은 " + my_sum + "입니다");
    }
    public static int Add(int my_input) {
        if (my_input > 0)
            return my_input + Add(my_input - 1);
        else
            return my_input;
    }
}

출력

정의된 숫자는 25입니다
25까지의 자연수의 합은 325입니다

참고: 등차수열 공식

재귀 대신 수학 공식 n × (n + 1) / 2를 사용하면 반복 호출 없이도 1부터 n까지의 합을 즉시 구할 수 있습니다. 다만 재귀의 기본 원리를 학습하는 목적이라면 위의 Add 함수가 가장 좋은 예제가 됩니다. 한 가지 주의할 점은 입력값이 매우 클 경우 재귀 호출이 깊어져 스택 오버플로(StackOverflowError)가 발생할 수 있다는 것입니다.