[알고리즘-PS] Java 에서 재귀 호출로 팩토리얼을 구현하는 방법

재귀

 

재귀의 뜻

재귀란 본래의 것으로 다시 돌아가는 것을 말 한다고 구글 검색에서 발췌해 왔다.

이 말은 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 이를 재귀적(Recursive) 이라고 한다.

 

본래의 것으로 다시 돌아간다는 것을 좀더 직관적으로 보여주자면

 

화면안에 또 화면안을 호출하는 방송사고

이러한 것들이 바로 재귀이다.

재귀 호출

프로그래밍에서도 이런 재귀적 효과를 이용하면 좀 더 간결한 프로그래밍을 구사할 수 있는데 재귀 호출을 가장 잘 표현할 수 있는 것이 팩토리얼 이다.

 

팩토리얼

 

팩토리얼은 1부터 N 까지의 모든 수를 곱하는 것인데, 다음과 같이 느낌표로 팩토리얼을 정의한다.

 

 

이 과정을 코드로 만들어 보자면 다음과 같다

 

재귀 호출을 사용하지 않은 팩토리얼 함수

 

class Main {

    int factorialNonR(int num){
        int ans = 1;
        for (int i = 1; i <= num; i++) {
            ans = ans * i;
        }

        return ans;
    }
}

 

위와 같이 재귀 호출을 사용하지 않으면 for문을 이용하여 i 부터 1 까지의 모든 곱을 ans 라는 변수에 저장하고 return 하게 된다.

 

하지만 재귀를 사용하단다면 더욱 간결하고 직관적인 코드가 될 것이다.

 

재귀 호출을 사용한 팩토리얼 함수

class Main{

    int factorial(int num){
        if(num > 0) return num * factorial(num-1);
        else return 1;
    }

 }

 

if절에서 보면 return 을 하는데 현재의 num과 factorial(num-1)의 호출 결과를 곱하는데, 또 factorial(num-1) 은 factorial(num-1) * factorial(num-2)로 나눠질 수 있다.

 

점점 수행하다가 n이 0이 되는 순간 1을 리턴해서 다시 상향식으로 올라간다.