11.07.(월) Java-13: 재귀 함수

재귀 함수

재귀함수란 함수가 본인과 동일한 함수를 반복해서 불러오는 함수다.

우리가 배운 for문을 함수 하나로 표현한 것과 같다고 생각하면 된다.

이러한 구조는 반복문보다 간결하고 이해하기 쉽지만, 익숙하지 않은 사람들에겐 더욱 어렵게 다가올 수 있다.

예시로 배열을 만드는 코드를 짜보자.

public class Array {
	static int[] arr = {50, 60, 80, 30, 40};
	
	// 배열의 값을 반복문을 이용하여 출력하기
	public static void printArray1() {
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
		
		for(int i : arr) {
			System.out.print(i + " ");
		}
		System.out.println();
	}
	
	// 재귀호출을 이용한 배열의 값 출력하기
	public static void printArray2(int i) {	// i = 0 (초기값)
		if(i==arr.length) {
			System.out.println();
			return;
		}
		System.out.print(arr[i] + " ");
		printArray2(++i);
	}
	
	
	public static void main(String[] args) {
		printArray1();
		printArray2(0);
	}
}

arr 배열에 있는 숫자들을 출력하는 함수들이다.

printArray1()은 반복문을, printArray2()는 재귀호출을 이용하여 출력했다.

이 둘의 가장 큰 차이점을 꼽자면, 반복문은 단 하나의 printArray1()이라는 메소드에서 출력했고, 재귀함수는 배열의 크기인 5만큼 각각 다른 printArray2() 메소드를 만들어서 출력했다.

원리

재귀함수의 작동방식은 이러하다. 위의 printArray2()를 예로들어 설명하자면, 가장 먼저 입력값 0을 가지는 printArray2(0)이 실행된다.

메소드 안에 들어와서 가장 처음 보이는 if 조건문을 살펴보면, 입력받은 정수형 i 변수가 arr배열의 크기와 같은지 확인한다.

if(i==arr.length) {}

arr배열의 크기는 5이므로, 조건이 맞지 않기 때문에 조건문은 넘어가고, print 명령어로 입력값의 index에 위치한 arr배열값을 출력해준다.

System.out.print(arr[i] + " ");

그리고 제일 중요한 마지막 부분에서는 자신과 같은 printArray2() 함수를 호출하는데, 입력값이 ++i 임을 확인할 수 있다.

재귀호출을 마주하기 전까지는 i는 0이었지만, ++연산자가 변수 앞에 붙었기 때문에 연산을 먼저 해주고 난 다음, 입력값으로 적용된다.

그렇기 때문에 해당 재귀호출은 printArray2(1)이고, 새로운 함수를 불러왔음을 확인했다.

printArray2(++i);

이와 같은 방식으로 반복을 해준다. printArray2(2), printArray(3), printArray(4), 그리고 printArray2(5).

여기서 입력값이 5가 되어야 비로소 이때까지 넘겨왔던 조건문에 걸린다. 조건문의 내용을 살펴보면 빈 줄을 출력하고 return으로 함수를 종료시킨다.

if(i==arr.length) {
	System.out.println();
	return;
}

반환형이 void인 printArray2() 함수는 아무 값도 반환하지 않은 채 역순으로 다시 printArray(5)의 return에서 출발해서 printArray(0)까지 도착하면 끝이 난다.

 

이러한 처리방식에서의 차이점은 메모리 구조에서 스택을 반복적으로 사용하기 떄문에 일반적인 반복문보다 메모리를 더 많이 쓰고 속도에서 성능저하가 발생한다.