Computer >> 컴퓨터 >  >> 프로그래밍 >> Java

자바 재귀(Recursion) 완벽 가이드: 개념부터 실전 예제까지

프로그래밍에서 재귀(recursion)란 함수가 자기 자신을 직접 또는 간접적으로 호출하는 과정을 의미합니다. 재귀는 컴퓨터 과학의 다양한 문제를 해결하는 데 널리 활용되는 핵심 개념입니다.

자바(Java)는 스스로를 호출하는 메서드, 즉 재귀 메서드를 만드는 것을 지원합니다.

이 글에서는 예제를 통해 재귀가 어떻게 동작하는지, 그리고 자바에서 재귀 함수를 어떻게 작성하는지 살펴보겠습니다. 이 가이드를 끝까지 읽고 나면 자바에서 전문가처럼 재귀 메서드를 작성할 수 있을 것입니다.

자바 메서드의 기본

메서드(method)는 흔히 함수라고도 불리며, 특정 작업을 수행하는 코드 블록입니다. 예를 들어 배열에 담긴 값들의 합계를 계산하거나, 배열의 내용을 콘솔에 출력하는 작업을 메서드로 처리할 수 있습니다.

자바에서 메서드를 선언하는 기본 문법은 다음과 같습니다.

modifier static returnType methodName (Parameters) {
	// 메서드 본문
}

예를 들어, 콘솔에 "수요일입니다! 한 주의 절반이 지났습니다!"라는 문장을 출력하는 메서드를 만들고 싶다면 아래와 같이 작성할 수 있습니다.

class Main {
public static void printItsWednesday() {
	System.out.println("It's Wednesday! We're half-way through the week!");
}

public static void main(String[] args) {
	printItsWednesday();
}
}

printItsWednesday() 메서드를 호출하면 다음과 같은 결과가 출력됩니다.

It's Wednesday! We're half-way through the week!

자바 메서드에 대해 더 깊이 알고 싶다면, 자바 메서드 완전 정리 가이드를 참고해 보시기 바랍니다.

위 예제에서는 메인 프로그램 안에서 printItsWednesday() 메서드를 호출했습니다. 하지만 만약 메서드 내부에서 그 메서드 자신을 호출한다면, 바로 재귀 메서드가 되는 것입니다.

자바에서의 재귀 동작 원리

재귀 메서드는 처음에는 메인 메서드에서 호출되지만, 이후에는 메서드 자신의 내부에서 다시 호출되는 메서드입니다. 재귀 메서드의 기본 구조는 다음과 같습니다.

static void executeMethod() {
	// 여기에 코드 작성
	executeMethod(); // 이 부분이 재귀 호출입니다
	// 여기에 코드 작성
}

public static void main(String[] args) {
	executeMethod(); // 일반적인 메서드 호출
}

프로그램을 실행하면 메인 프로그램에서 executeMethod() 메서드가 호출됩니다. 그러면 executeMethod() 내부의 코드가 실행되는데, 이 코드 안에는 executeMethod() 호출이 포함되어 있습니다. 결국 프로그램은 반복 루프에 진입하게 됩니다.

프로그램은 재귀 실행을 멈추는 조건이 충족될 때까지 executeMethod() 메서드를 계속 실행합니다. 만약 재귀를 중단할 조건이 없다면 프로그램은 영원히 실행되며, 이를 무한 재귀(infinite recursion)라고 부릅니다.

그렇다면 왜 재귀를 사용해야 할까요? 첫째, 특정 상황에서 재귀는 프로그램의 시간 복잡도를 줄여줄 수 있습니다. 둘째, 재귀를 활용하면 일부 알고리즘을 더 읽기 쉽고 유지보수하기 좋은 방식으로 구현할 수 있습니다.

재귀로 자주 작성되는 대표적인 프로그램 예시는 다음과 같습니다.

  • 피보나치 수열 계산
  • 문자열 뒤집기
  • 숫자의 팩토리얼 계산
  • 이진 트리의 높이 계산

다만 재귀는 일반적인 메서드로 작업을 처리하는 것보다 느려질 수 있다는 점에 유의해야 합니다. 그 이유는 재귀 메서드가 실행될 때마다 변수를 위한 새로운 저장 공간이 생성되기 때문입니다.

자바 재귀 실전 예제

이제 두 가지 예제를 통해 자바에서 재귀가 실제로 어떻게 동작하는지 확인해 보겠습니다.

예제 1: 재귀로 문자열 뒤집기

중학교 교사를 위해 학생의 연간 성적이 담긴 문자열을 뒤집어주는 프로그램을 만든다고 가정해 보겠습니다. 이 문자열은 학생이 받은 첫 번째 성적으로 시작해서 가장 최근의 성적으로 끝납니다. 우리는 문자열을 뒤집어서 가장 최근 성적이 맨 앞에 오도록 만들고 싶습니다.

다음 코드를 사용하면 문자열을 뒤집을 수 있습니다.

public class ReverseGrades {
	public static String reverse(String grades) {
		if (grades.isEmpty())
			return grades;
		return reverse(grades.substring(1)) + grades.charAt(0);
	}

	public static void main(String[] args) {
		String grades = "CBCBAABACAABA";
		String reverse_grades = reverse(grades);

		System.out.println("This student's grades for the year are: " + reverse_grades);
	}
}

코드를 실행하면 다음과 같은 결과가 출력됩니다.

This student's grades for the year are: ABAACABAABCBC

위와 같이 프로그램이 문자열의 내용을 성공적으로 뒤집었습니다. 이 프로그램에서는 reverse()라는 이름의 재귀 함수를 만들었습니다.

reverse() 함수가 실행되면 먼저 성적 문자열이 비어 있는지 검사합니다. 비어 있다면 성적 목록을 메인 프로그램에 그대로 반환합니다. 이 시점에서 함수 마지막의 reverse() 호출이 실행될 기회를 얻지 못하므로 재귀가 종료됩니다.

성적 문자열이 비어 있지 않다면, 프로그램은 reverse() 메서드를 다시 실행하고 그 결과를 문자열의 첫 번째 문자와 연결합니다. 예제에서는 charAt() 메서드를 사용해 문자열의 첫 번째 문자를 가져온 뒤, reverse() 메서드의 반환값 왼쪽에 붙이는 방식으로 동작합니다.

문자열 뒤집기가 완료되면 "This student's grades for the year are:"라는 메시지와 함께 뒤집힌 성적 문자열이 프로그램에 반환됩니다.

예제 2: 재귀로 팩토리얼 계산하기

재귀가 유용하게 활용되는 또 다른 사례는 숫자의 팩토리얼을 계산하는 것입니다.

수학에서 팩토리얼(factorial)은 어떤 수 이하의 모든 양의 정수를 곱한 값입니다. 예를 들어 5의 팩토리얼은 5*4*3*2*1, 즉 120입니다. 팩토리얼 계산은 반복적인 곱셈 연산을 포함하기 때문에, 재귀로 문제를 해결하기 좋은 실생활 예제 중 하나입니다.

다음 자바 프로그램은 숫자 7의 팩토리얼을 계산합니다.

class Main {
	static int calculateFactorial(int number) {
		if (number != 0)
			return number * calculateFactorial(number-1);
		else
			return 1;
	}
	
	public static void main(String[] args) {
		int num = 7;
		int answer = calculateFactorial(num);
		System.out.println("The factorial of 7 is: " + answer);
	}
}

코드를 실행하면 다음과 같은 결과가 출력됩니다.

The factorial of 7 is: 5040

이 예제에서는 calculateFactorial()이라는 메서드를 만들어, number 매개변수에 저장된 값에 다음 calculateFactorial() 호출의 결과를 곱하도록 했습니다. 이 과정은 number 매개변수가 0이 될 때까지 반복됩니다.

number 매개변수가 0이 되면 코드의 if 문이 1을 반환하고, calculateFactorial() 메서드의 최종 결과가 메인 프로그램으로 전달됩니다.

즉, calculateFactorial() 메서드는 7*6*5*4*3*2*1을 차례로 계산한 뒤 그 답을 메인 프로그램에 반환합니다. 계산이 완료되면 "The factorial of 7 is:"라는 메시지와 함께 프로그램이 구한 답이 콘솔에 출력됩니다.

마무리

재귀는 메서드가 자기 자신을 호출하는 프로그래밍 개념입니다. 재귀 메서드는 같은 작업을 여러 번 반복하면서 이전 반복의 결과를 현재 반복에 활용해야 하는 경우에 특히 유용합니다.

이 글에서는 자바에서 재귀의 기본 개념과 재귀 메서드를 만드는 방법을 살펴보았습니다. 또한 문자열 뒤집기와 팩토리얼 계산이라는 두 가지 예제를 통해 재귀가 실제로 동작하는 모습도 확인했습니다.

이제 여러분도 전문가처럼 자바에서 재귀 메서드를 활용할 준비가 되었습니다!