자바의 반복문과 재귀함수

포모·2020년 12월 17일

Clean Code

목록 보기

5/6

거의 1년 넘는 시간동안 알고리즘을 공부해오면서 느낀 것은 재귀 함수보다는 반복문이었습니다.
성능 측면에서 반복문이 압도적으로 우세했기 때문이었습니다.

그러나 클린 코딩에서는 그렇지 않았습니다.

private void inputCarName() {
    while (true) {
        try {
            CarController.askCarName();
        } catch (NullPointerException e) {
            break;
        }
    }
}

<자동차 경주 게임>의 자동차 이름을 입력 받는 부분인데요,
while 문과 try~catch 문이 사용되면서 코드의 가독성이 저하되고 indent도 2가 됩니다.

그렇다면 재귀함수를 사용하면 어떻게 될까요?

private void inputCarName() {
    try {
        CarController.askCarName();
    } catch (NullPointerException e) {
        inputCarName();
    }
}

indent는 1로 줄어들면서 훨씬 가독성이 좋은 코드가 되었습니다.
그러나 재귀 깊이가 깊어짐에 따라 반복문을 사용했을 때 보다 성능이 저하됩니다.

재귀 함수는 기본적으로 스택 메모리를 사용하는데, 재귀가 깊어짐에 따라 stackoverflow가 발생하면서 프로그램이 비정상적 종료됩니다.

Stack overflow란?
함수를 호출하면 함수에 대한 모든 정보(변수, 리턴 값 등)와 리턴 후의 위치가 스택 메모리에 저장됩니다.

재귀가 깊어짐에 따라 스택 메모리에 쌓이게 되고 메모리를 초과하여 Stack overflow가 발생하게 됩니다.

또한 함수가 호출/종료될 때마다 스택 프레임을 구성/해제하는 과정에서 반복보다 많은 오버헤드가 들기 때문에 속도가 훨씬 느려집니다.

Overhead란?
어떤 처리를 위한 간접적 처리 시간, 메모리 등을 의미합니다.

tail call recurstion

이를 해결하기 위한 것이 꼬리 재귀 라고 하는데요.

함수가 리턴된 후 아무 작업도 하지 않는 것을 꼬리 호출이라 하고, 이 구조를 꼬리 재귀라 하며, 이런 함수를 꼬리 재귀 함수라고 합니다.

function factorialTail(n, acc) {
	if (n === 1) return acc;
	return factorialTail(n - 1, acc * n); 
}
function factorial(n) {
	return factorialTail(n, 1);
}