[백준]10872번 팩토리얼 (꼬리 재귀 이용함)

문제

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(0 ≤ N ≤ 12)이 주어진다.

출력

첫째 줄에 N!을 출력한다.

 

알고리즘 분류 

수학 , 구현, 조합론 

 

 

 

처음 구현한 코드는 다음과 같다. 

// 백준 10872번 
// n! 출력하기 . 

package codingTest;

import java.util.Scanner;

public class Algorithm3 {

	 static int factorial(int n) {

		if (n <= 1) {
			return 1;
		}

		return factorial(n - 1) * n;

	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		System.out.println(factorial(sc.nextInt()));

	}

}

콘솔상에서는 잘 작동하였지만 스텍 오버플로우가 발생할 수도 있다.

그러므로 다른 방법으로도 코드를 구현해 보고자한다.. 

이를 해결하고자 코드를 다시 구성하여 주었다. 

함수를 호출 할 때 함수의 파라미터, 리턴값, 복귀주소등이 스텍에 저장되는데 재귀함수를 사용하면 호출한 함수가 종료되지 않은채 새로운 함수를 호출하게 되므로 스택에 매모리가 계속적으로 저장되게 되므로 스텍 메모리에 더이상 가용할

메모리가 없는 경우 스택 오버 플로우가 발생하게 된다. 

 

함수를 종료하지 않고 계속해서 호출해서 생긴 문제이므로 이전에 호출한 함수를 종료하면된다. 

즉 함수 호출 시 이전의 호출한 스텍 메모리를 종료하는 것인데 이를 꼬리 재귀라고도 부른다고 한다. 

구현방법 : 다음 함수 호출시 현재 함수의 연산된 결과를 전달 하면된다. 그러면 함수 종료시 이전 함수의 데이터와 연산할 필요가 없음으로 스택 메모리의 이전함수 데이터를 따로 저장할 필요가 없어진다. 

 

 

꼬리재귀를 이용한 모습 

// 백준 10872번 
// n! 출력하기 . 

package codingTest;

import java.util.Scanner;

public class Algorithm3 {

	 static int factorial(int n, int total) {

		if (n <= 1) {
			return total;
		}

		return factorial(n-1, n*total);

	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		System.out.println(factorial(sc.nextInt(),1));

	}

}

 

(설명)

예를들어 (3,1) 을 입력한다고 가정해보자 그러면 

(3,1) >>(2,3) >>(1,6) >> 어? 1 이네 total을 return하자 라고 해서 6 을 리턴한다.