재귀 함수 이해하기(자바)

먼저 알고리즘을 설계하기전에 재귀함수가 어떤 것인지만 간단하게 올고 넘어가자.

 

• 재귀함수란 자신의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미합니다. 다른 말로는 재귀호출, 되부름이라고 부르기도 합니다. 반복문을 사용하는 코드는 항상 재귀함수를 통해 구현하는 것이 가능하며 그 반대도 가능합니다.

• 재귀함수를 작성할 때는 함수내에서 다시 자신의 함수을 호출한 후 그 함수가 끝날 때 까지 함수 호출 이후의 명령문이 수행되지 않는 다는 사실과 종료조건(base case)이 꼭 포함 되어야한다는 부분을 인지하고 작성하면 무한루프를 방지할 수 있습니다.

간단한 예제 팩토리얼 함수를 만들어서 이해해 보자.

 

먼저 팩토리얼(!)이란 수학에서, 자연수의 계승 또는 팩토리얼은 그 수보다 작거나 같은 모든 양의 정수의 곱이다. n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말이다. 즉 1 부터 n 까지의 모든 자연수의 곱이다.

4! = 4*3*2*1

7! = 7*6*5*4*3*2*1

2! = 2*1

 

---

자바 코드

 

public class Factorial {

    public static void main(String[] args) {

        int n = 4; 
        System.out.println(factorial(n));

    }

    public static int factorial(int n) {
        if (n <= 1)
            return n;
        else 
            return factorial(n-1) * n;
    }
}

---

이 처럼 재귀 함수는 하위 작업을 수행하도록 자기 자신을 호출하여 작업을 수행한다. 어느 단계에 이르러서는, 자기 자신을 호출하지 않는 것을 기본 경우라고 하고, 함수가 자기 자신을 호출해서 하위 작업을 수행하는 것을 재귀 경우라고 한다. 

n이 1보다 큰 재귀 경우에는 함수는(n-1)!의 값을 구하기 위해 자기 자신을 호출하여 그 결과를 n에 곱한다. n이 0이거나 1인 기본 경우에는, 함수는 1을 리턴한다. 

 

재귀와 반복 비교

 

재귀

• 기본 경우에 도달하면 종료한다.
• 각 재귀 호출은 스택 프레임(메모리)에 부가 공간을 필요로 한다.
• 무한 재귀에 들어가게 되면 메모리 용량을 초과해서 스택 오버플로우를 초래하게 된다.
• 어떤 문제들의 해답은 재귀적인 수식으로 만들기 쉽다.

반복

• 조건이 거짓이 될 때 종료한다.
• 각 반복이 부가 공간을 필요로 하지 않는다.
• 무한 루프는 추가 메모리가 필요하지 않으므로 무한히 반복된다.
• 반복적 해법은 재귀적 해법에 비해 간단하지 않을 때가 있다.

 

재귀에 대한 참고 사항

• 재귀적 알고리즘에는 두 가지 경우, 재귀적 경와 기본 경우가 있다.
• 모든 재귀 함수는 기본 경우에 종료해야 한다.
• 일반적으로 반복 해법이 재귀 해법보다 효율적이다.(재귀 호출에 따른 부가적인 메모리 요구 때문.)
• 재귀 알고리즘은 스택을 이용해서 재귀 호출 없이 구현될 수 있지만 보통 문제를 더 일으키기 떄문에 유용하지 못하다. 이 맣은 재귀적으로 풀 수 있는 문제는 반복적으로 풀 수도 있다는 말이다.
• 어떤 문제들의 경우엔 눈에 띄는 반복적 알고리즘이 없을 수도 있다.
• 어떤 문제는 재귀적 해법이 최적이고, 어떤 문제는 그렇지 않다.