[JAVA] 재귀함수를 사용한 Factorial

오늘은 신입 면접시 자주가끔???(?) 나오는 재귀 함수에 대한 포스팅을 해보도록 하겠습니다.

더불어 재귀함수와 자주 비교되는 반복문에 대해서도 같이 작성하도록 하겠습니다.

 

재귀함수란?

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 문제를 해결하는 방법

 

반복문은 while문이나 for문의 사용을 통해 익숙할 것입니다.

하지만 재귀함수는 비슷한 기능임에도 조금은 낯설다고 생각합니다. (고수분들 제외)

 

재귀함수에서 가장 쉬운 문제인 Factorial을 사용하여 이해를 돕도록 하죠.

팩토리얼은 예를들면 5! [5 팩토리얼] 이라고 하면 5x4x3x2x1 = 120 의 결과를 얻는 것입니다.

이러한 문제에 직면했을 때 쉽게 생각하는 방법 중 하나가 반복문을 이용하는 것이죠

 

재귀 함수에 앞서서, For문을 이용해서 Factorial 을 구현해 보도록 하겠습니다.

---

For문을 이용한 Factorial 구하기

//반복문을 이용한 재귀함수로 factorial 구하기
 
public class for_factorial {
    
    public static int factorial(int num) {
        System.out.print(num + "! = ");
        int sum = 1;
        for(int i = num; i>=1; i--) {
            sum *= i; // 반복문을 통해 i값의 곱을 sum에 결과값 저장
            if(i == 1) {
                System.out.print(i + " = ");
            }else {
                System.out.print(i +" x ");
            }
            
        }
        return sum;
    }
    
    public static void main(String[] args) {
        System.out.println(factorial(5));
    }
 
}

결과값

 

---

그런데 재귀 함수는 자기자신을 다시 호출하여 사용한다고 하였습니다.

그렇다면 재귀함수를 통하여 구현해보도록 하겠습니다.

 

재귀함수를 이용하여 Factorial 구하기

public class Factorial {
    // 재귀함수로 factorial 구하기
    public static int factorial(int num) {
        if (num == 1)
            return 1;
        else
            System.out.println("factorial(" + num + ")"); //몇번 호출했는지 확인해보죠
            return num * factorial(num - 1);
 
    }
 
    public static void main(String[] args) {
 
        System.out.println(factorial(5));
    }
 
}
 

 

결과값

조금 명시적으로 이해를 돕기위해 다음과 같이 출력값을 확인했습니다.

 

For문에 비해 간결해진 코드를 확인할 수 있습니다.

일반 반복문을 통해 구현 가능한 기능은 재귀함수를 이용해서도 구현이 가능합니다.

반대로 재귀함수로 구현한 기능은 반복문을 통해서도 구현이 가능하죠.

그렇다면 왜 재귀함수를 사용하는 것일까요 ?

---

재귀함수의 사용 이유

재귀함수의 사용이유는 위와 같이 간결해진 코드를 말할 수 있습니다.

가독성이 높아진다 라고 말할 수 있죠.

그런데 For문에 비해 재귀함수를 이용하면 속도도 떨어지고, 메모리 낭비도 심해집니다.

이러한 문제가 있음에도 재귀함수가 사용되는 이유가 무엇일까요?

 

1. 동적프로그램이나 병합정렬, 그래프탐색알고리즘 등의 특정한 부분의 개발에 유리하다.
2. 가독성이 높다.
3. 변수의 사용을 줄여준다.

 

저 또한 For문과 재귀함수의 정확한 사용 이유에 대해 많은 검색을 해보았고, 이러한 결과를 말할 수 있다고 생각합니다.

하나씩 제가 이해한 부분에 대해 말해보도록 하겠습니다.

 

1. 병합정렬 등을 반복문으로 구현하려면 재귀함수를 사용하는 것에 비해 매우 복잡하다고 말할 수 있습니다.

이는 추가적으로 정렬을 포스팅할 때 이야기를 해보도록 하겠으며, 지금은 그러하다 라고 하고 넘어가도록 하죠

 

2. 가독성이 높다는 것이 100%라고 말하기는 어렵습니다.

재귀 호출이 어떠한 코드에서는 For문에 비해 이해가 어려울 수도 있지만, 대체적으로 높다라고 생각하시면 좋을 듯 합니다.

 

3. 변수의 사용을 줄여준다.

이부분은 검색을 통해 알게된 사실입니다.

https://kldp.org/node/134556

링크를 통해 확인해 보시면 좋을 듯 합니다.

간단히 요약하면 mutable state(변경 가능한 상태)를 제거해줌으로써 프로그램의 오류를 줄일 수 있다는 이야기 입니다.

 

위 코드만 보아도, For문에는 변수가 2개, 재귀함수에는 한개도 없는 것을 말할 수 있습니다.

 

---

아주 간단한 재귀적 문제를 다뤄보았습니다.

재귀함수의 사용은 간결한 코드 작성에 용이하지만, 때에 따라서 비효율적인 코드사용일 수 있기 때문에 프로그래밍을 함에 있어서 이러한 부분에 대한 고민을 하면서 적절하게 사용하는 것이 중요할 것입니다.

 

 

개인적인 공부 이기 때문에 틀린 내용이 있다면 댓글 부탁드립니다.