[ALGORITHMS]문제 04. 팩토리얼 구하기

문제 4 

팩토리얼 구하기

1부터 n까지 연속한 정수의 곱을 구하는 알고리즘을 만들어보세요

이번 문제는 1부터 n까지의 곱, 즉 팩토리얼(factorial)을 구하는 문제입니다.

1. 팩토리얼

팩토리얼은 숫자 뒤에 느낌표(!)를 붙여 표기하며 1부터 n까지 연속한 숫자를 차례로 곱한 값입니다. '계승'이라고도 합니다.

1! = 1

3! = 1 x 2 x 3 = 6

n! = 1 x 2 x 3x ... x (n-1) xn

단 0!은 1이라고 약속합니다.

팩토리얼을 구하는 프로그램은 문제 1에서 살표본 1부터 n까지의 숫자 더하기를 조금 고치면 수비게 만들 수 있습니다.

덧셈 연산을 곰셉연산으로 바꾸고, 계산의 초깃값을 0에서 1로만 고치면 팩토리얼 프로그램을 간단히 만들 수 있습니다.

* 팩토리얼을 구하는 알고리즘 1

2. 러시아 인형

다음에는 팩토리얼 구하기를 재귀호출로 알아보기 전에 '마트료시카'라고 부르는 러시아 인형 이야기를 해보도록 하겠습니다.

마트료시카 인형은 이렇게 생겼는데 이 인형들은 큰 인형을 열면 그 안에 비슷하게 생긴 작은 인형이 있고 이처럼 인형이 계속 반복되어 나오다가 더 작게 만들기 힘들 정도로 작은 마지막 인형이 나오는데, 그 마지막 인형 안에는 작은 사탕이 들어 있기도 합니다.

다음은 러시아 인형의 특징입니다

 - 인형 안에는 자기 자신과 똑같이 생긴, 크기만 약간 작은 인형이 들어 있습니다.

 - 인형 안에서 작은 인형이 반복되어 나오다가 인형을 더 작게 만들기 힘들어지면 마지막 인형이 나오면서 반복이 끝납니다.

 - 마지막 인형 안에는 사탕이나 초콜릿 같은 작은 상품이 들어 있기도 합니다.

러시아 인형의 특징을 잘 기억하면서 재귀호출이 무엇인지 공부해봅시다.

3. 재귀 호출 : 다시 돌아가 부르기

hello() 함수의 정의를 보면 "hello"라는 문장을 화면에 출력한 다음 자기 자신인 hello()를 다시 호출합니다. 이것이 바로 재귀 호출입니다.

"hello"를 출력하고 다시 자기 자신을 호출하고 이걸 영원히 반복해서

이렇게 무한 루프에 빠지게됩니다

이 프로그램이 재귀 호출이 무엇인지 알려주는 예제이지만 올바른 재귀 호출 프로그램은 아닙니다.

종료조건이 없기 때문입니다. 종료조건 즉 특정 조건이 되면 더는 자신을 호출하지 않도록 설계되어야만 합니다.

그렇지 않으면 계속 반복하다가 재귀 에러가 나버립니다.

재귀 호출 함수가 계산 결과를 돌려줄 때는 return 명령을 사용해서 종료 조건의 결괏값부터 돌려줍니다.

종료 조건의 결괏값은 곧 마지막으로 호출된 함수의 결과값입니다.

4. 재귀 호출 알고리즘

팩토리얼을 재귀 호출로 표현하면 다음과 같습니다

1! = 1

2! = 2 x 1 = 2 x 1!

3! = 3 x (2 x 1) = 3 x 2!

4! = 4 x (3 x 2 x 1) = 4 x 3!

...

n! = n x (n-1)!

여기서 1!=1 그리고 n! = n x (n-1)!이라는 팩토리얼의 성질을 이용해서 팩토리얼을 구하는 프로그램을 만들어 보았습니다.

* 팩토리얼을 구하는 알고리즘 2

* 분석 해 보기

fact(4)

-> 4 * fact(3)

-> 3 * fact(2)

->2 * fact(1)

-> 1

-> 2 * 1

-> 3 * 2 * 1

-> 4 * 3 * 2 * 1 = 24

5. 알고리즘 분석

fact(4)를 계산 과정을 보면 fact(4)를 구하려면 fact(1)의 종료 조건으로 돌려받은 1을 2와 곱하여 돌려줍니다

그리고 그 값에 다시 3을 곱하여 돌려주고, 다시 그 값에 4를 곱하여 돌려주므로 곱셈이 모두 3 번 필요합니다. 마찬기로 n!을 구하려면 곱셈이 모두 n-1번 필요하다는 것을 알 수 있습니다

따라서 반복문을 이용한 알고리즘이나 재귀 호출을 이용한 알고리즘의 계산 복잡도 모두 O(n)입니다

*연습문제

4 - 1 문제 1의 1부터 n까지의 합 구하기를 재귀 호출로 만들어보세요

4 - 2 문제 2의 숫자 n개 중에서 최댓값 찾기를 재귀 호출로 만들어보세요

읽어주셔서 감사합니다