[재귀]03. 반복문 vs 재귀

동일한 로직을 여러 번 적용하기 위해서는 반복문을 적용할 수 있는데 이 반복문은 재귀의 형태로 변경이 가능하다. 그런데 일반적으로 사람들은 반복문에 상대적으로 익숙하기 때문에 굳이 당장 손이 가지않는 재귀를 사용하려 하지 않는다. 하지만 알고리즘에서 재귀는 선택이 아닌 필수이다.!

이번 포스트에서는 반복문과 재귀를 비교해보고 최종적으로 왜 재귀를 써야하는지 살펴보자.

 

반복문 vs 재귀

 

반복문과 재귀 함수의 비교

일반적으로 반복문과 재귀 함수는 다음과 같이 비교할 수 있다.

	재귀 함수	반복문
종료 조건	기본 파트에서 return	반복문 종료 조건
수행 시간	메서드 호출 비용으로 상대적으로 느림	상대적으로 빠름
메모리	stack 메모리 점유로 상대적으로 많이 사용	상대적으로 적게 사용
작성 난이도	이해하면 사람의 표현	기계적 반복
제어문 형태	if~else의 선택 구조	for, while의 반복 구조
무한 반복 시	StackOverflowError 발생	CPU 무한 점유

얼핏 비교해보면 메모리적으로나 수행 시간적으로 재귀를 이용하는 것 보다 반복문을 이용하는편이 훨씬 유리해보인다.

 

 

하지만 결정적으로

하지만 결정적으로 문제의 크기가 동적일 경우 재귀는 메모리가 허락한다면 자유롭게 표현이 가능하지만 반복은 사용하기가 어렵다. 예를 들어 {a, b, c, d}4개의 원소에서 3개를 뽑는 순열을 구한다고 했을 때 배열은 아래처럼 구현할 수 있다.

static char[] src = {'a', 'b', 'c', 'd'};


static void makePermLoop() {
    for (int i = 0; i < src.length; i++) {
        for (int j = 0; j < src.length; j++) {
            if (j != i) {
                for (int k = 0; k < src.length; k++) {
                    if (k != i && k != j) {
                        System.out.printf("%d - %c, %c, %c%n", ++cnt, src[i], src[j], src[k]);
                    }
                }
            }
        }
    }
}

이 상황에서 4P2를 구해야한다면 for 문의 구조를 변경하기가 매우 어렵다.

 

만약 재귀를 이용해서 순열을 구한다면 아래와 같이 작성해볼 수 있다.

static void makePerm(int toChoose, boolean[] visited, char[] choosed) {
    if (toChoose == 0) {
        System.out.printf("%d - %s%n", ++cnt, Arrays.toString(choosed));
        return;
    }

    for (int i = 0; i < src.length; i++) {
        if (!visited[i]) {
            visited[i] = true;
            choosed[toChoose - 1] = src[i];
            makePerm(toChoose - 1, visited, choosed);
            visited[i] = false;
        }
    }
}

이 경우에는 몇 개를 뽑아야 하는지에 대한 toChoose만 변경하면 손쉽게 4P2, 4P3을 구할 수 있다.

 

따라서 알고리즘에서 재귀는 선택이 아닌 필수이다.

 

 

재귀는 정말 중요해요!

사실 알고리즘 뿐 아니라 일반 프로그래밍에서도 재귀의 활약은 매우 중요하다. 쉬어가는 느낌으로 재귀의 중요성에 대해 이야기한 사람들의 명언을 살펴보자.

 

L.Peter Deutsch(PDF interpreter, GhostScript, PostScript 창시자)

To iterate is human, to recurse divine.(사람은 반복문을 쓰고 신은 재귀함수를 쓴다.) 난 사람인뎅. ㅜㅜ

 

Leigh Coldwell(Stackoverflow.com 고수)

Loops may archieve a performance gain for your program, Recursion may archieve a performance gain for your programmer. Choose which is more important in your situation!(반복문은 프로그램의 성능을 향상시킬 수 있지만 재귀는 프로그래머의 성능을 향상시킬 수 있다. 상황에 따라 어떤 것이 중요한지 선택하라!)  하지만 알고에서 재귀는 선택 사항이 아니다.!