재귀(Recursion)를 활용해 두 숫자의 곱을 구하는 Java 프로그램

이 글에서는 재귀(recursion)를 사용하여 두 숫자의 곱을 구하는 방법을 알아봅니다. 재귀 함수란 특정 조건이 만족될 때까지 자기 자신을 반복적으로 호출하는 함수를 의미합니다.

재귀란 무엇인가?

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

대부분의 프로그래밍 언어는 스택(stack)을 통해 재귀를 구현합니다. 일반적으로 어떤 함수(호출자, caller)가 다른 함수 또는 자기 자신(피호출자, callee)을 호출하면, 호출자는 실행 제어권을 피호출자에게 넘기게 됩니다. 이 전달 과정에서 호출자가 피호출자에게 데이터를 함께 넘겨주기도 합니다.

입력 및 출력 예시

입력이 다음과 같다고 가정해 보겠습니다.

두 숫자 입력 : 12과 9

원하는 출력 결과는 다음과 같습니다.

12과 9의 곱은 108입니다

알고리즘

1단계 - 시작
2단계 - my_input과 my_result라는 두 개의 정수 변수 선언
3단계 - 사용자로부터 필요한 값을 읽어오거나 값을 직접 정의
4단계 - 두 개의 정수를 매개변수로 받는 재귀 함수 'getproduct'를 정의.
        이 함수는 기저 조건(base condition)에 도달할 때까지
        함수를 반복적으로 호출하며 곱을 계산한다.
5단계 - 재귀 함수 'getproduct'를 호출하고 그 결과를 저장
6단계 - 결과 출력
7단계 - 종료

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

아래 예제에서는 사용자가 직접 값을 입력합니다. 콘솔에서 두 숫자를 입력받은 뒤, 재귀 함수를 통해 곱을 계산하여 화면에 출력합니다.

import java.util.Scanner;
public class ProductRecursion{
   public static void main (String[] args){
      int my_input_1, my_input_2;
      System.out.println("필요한 패키지를 가져왔습니다");
      Scanner my_scanner = new Scanner(System.in);
      System.out.println("reader 객체가 정의되었습니다");
      System.out.print("숫자를 입력하세요 : ");
      my_input_1 = my_scanner.nextInt();
      System.out.print("숫자를 입력하세요 : ");
      my_input_2 = my_scanner.nextInt();
      System.out.println(my_input_1 +"과 " +my_input_2 +"의 곱은 " +getproduct(my_input_1, my_input_2) +"입니다");
   }
   static int getproduct(int my_input_1, int my_input_2){
      if (my_input_1 < my_input_2)
         return getproduct(my_input_2, my_input_1);
      else if (my_input_2 != 0)
          return (my_input_1 + getproduct(my_input_1, my_input_2 - 1));
      else
         return 0;
   }
}

출력 결과

필요한 패키지를 가져왔습니다
reader 객체가 정의되었습니다
숫자를 입력하세요 : 12
숫자를 입력하세요 : 9
12과 9의 곱은 108입니다

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

이번 예제에서는 정수 값이 코드 내에 미리 정의되어 있으며, 해당 값을 읽어와 콘솔에 출력합니다. 사용자 입력 없이 로직만 확인하고 싶을 때 유용한 방식입니다.

public class ProductRecursion{
   public static void main (String[] args){
      int my_input_1, my_input_2;
      my_input_1 = 12;
      my_input_2 = 9;
      System.out.println("두 숫자는 각각 " +my_input_1 +"과 " +my_input_2 +"(으)로 정의되었습니다");
      System.out.println(my_input_1 +"과 " +my_input_2 +"의 곱은 " +getproduct(my_input_1, my_input_2) +"입니다");
   }
   static int getproduct(int my_input_1, int my_input_2){
      if (my_input_1 < my_input_2)
         return getproduct(my_input_2, my_input_1);
      else if (my_input_2 != 0)
         return (my_input_1 + getproduct(my_input_1, my_input_2 - 1));
      else
         return 0;
   }
}

출력 결과

두 숫자는 각각 12과 9(으)로 정의되었습니다
12과 9의 곱은 108입니다

핵심 포인트 정리

위 재귀 함수 getproduct의 동작 원리를 살펴보면 다음과 같습니다.

1. 인자 교환: 첫 번째 수가 두 번째 수보다 작으면 두 인자의 순서를 바꿔 다시 호출합니다. 이렇게 하면 재귀 호출 횟수를 줄여 성능을 개선할 수 있습니다.

2. 덧셈 기반 곱셈: 두 번째 수가 0이 아니면, 첫 번째 수에 '첫 번째 수 × (두 번째 수 − 1)'의 결과를 더하는 방식으로 곱셈을 반복적인 덧셈으로 대체합니다.

3. 기저 조건: 두 번째 수가 0이 되면 0을 반환하며 재귀가 종료됩니다. 이 기저 조건이 없으면 스택 오버플로우(StackOverflowError)가 발생할 수 있습니다.