[JAVA] 자바 재귀호출과 팩토리얼 함수

재귀호출

재귀호출이란 함수 내부에서 해당 함수가 다시 호출되는 것을 의미합니다.

 

이러한 호출은 자기자신을 계속호출하기 때문에 끝없이 반복될 수 있으며

반드시 재귀호출을 중단하도록 조건 명령문을 반드시 포함해야 합니다.

 

사실 재귀호출은 자바만의 개념이라기 보다는 알고리즘에서 중요한 개념입니다.

즉, C 언어 JAVA 언어 가릴거 없이 모두 구현이 가능합니다.

 

 

재귀호출 팩토리얼 예제

1부터 10까지 곱하는 프로그램을 만든다고 가정해 봅니다.

 

먼저 1부터 10까지의 곱은 1에서 9까지의 곱의 곱하기 10 입니다.

다음 1부터 9까지의 곱은 1부터 8까지의 곱의 곱하기 9 입니다.

다음 1부터 8까지의 곱은 1부터 7까지의 곱의 곱하기 8 입니다.

....

다음 1부터 2까지의 곱은 1부터 1까지의 곱의 곱하기 2 입니다.

마지막 1부터 1까지의 곱은 1입니다.

 

 

이를 수도코드로 작성하면 다음과 같으며

프로그램으로 구현한 것과 동작방식을 표로 나타내 보았습니다.

 

1. n 이 1이 아니면, n 과  1 부터 n-1 까지의 곱을 곱한 값을 반환

2. n 이 1이면, 1을 반환

public class Test {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        
        int result = factorial(10);
        System.out.println(result);
    }
    
    public static int factorial (int num) {
        if (num == 1)
            return 1;
        
        return num * factorial ( num - 1 );
    }
}

위 코드의 흐름을 보면 아래처럼 표현이 가능합니다.

단계	코드의 흐름
1	10 * factorial ( 9 )
2	10 * 9 * factorial ( 8 )
3	10 * 9 * 8 * factorial ( 7 )
4	10 * 9 * 8 * 7 * factorial ( 6 )
5	10 * 9 * 8 * 7 * 6 * factorial ( 5 )
6	10 * 9 * 8 * 7 * 6 * 5 * factorial ( 4 )
7	10 * 9 * 8 * 7 * 6 * 5 * 4 * factorial ( 3 )
8	10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * factorial ( 2 )
9	10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * factorial ( 1 )
10	10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

 

 

재귀호출을 사용하는 이유

사실 재귀호출을 왜 사용해야 하는거지? 라는 의문이 들수도 있고

심지어 위와 같은 팩토리얼 코드는 반복문으로 간단하게 표현이 가능합니다.

 

재귀호출을 사용하는 이유는 코드의 목적과 가독성 입니다.

반복문으로 표현된 경우, 이 반복문이 어떤 목적인지 코드를 모두 해석해야 의미를 파악할 수 있습니다.

 

또한 재귀호출 방식이 조금 복잡하게 되는 경우는 어떻게 될까요?

예를들면 아래와 같은 피보나치 함수가 있으며, 이 함수를 반복문으로 표현하려면 훨씬 복잡하고 코드 이해에 더 많은 시간을 소요해야 할 것입니다.

public int fibonacci(int n) {
    if (n == 0) {
        return 0;
    }
    else if (n == 1) {
        return 1;
    }
    else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}