4. 팩토리얼 구하기 - 재귀 호출의 등장

* 책: 모두의 알고리즘 with 파이썬

1부터 n까지 연속한 정수의 곱을 구하는 알고리즘을 만들어 보세요. (=팩토리얼 구하기)

 

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

1부터 n까지의 합을 구하는 코드를 변형하여 만들기 가능 

#  구하는 방법1: 1부터 n까지의 합을 구하던 코드 변형
 
def fact(n):
    m = 1
    for i in range(1, n+1):
        m = m * i
    return m
 
fact(5) # 120

 

2. 팩토리얼을 구하는 알고리즘 ②: '재귀호출' 사용

    1) 재귀호출(recursion) 이란?: 함수 안에서 자기 자신을 부르는 것 

       - 재귀 호출 시 반드시 끊어주는 "종료 조건"이 있어야 함 

       - 재귀 호출 함수는 계산 결과 리턴 시 'return 종료 조건 결괏값' 부터 보여줌

# hello()를 끊임없이 부르는 함수
 
def hello():
    print("Hello, World!")
    hello() # hello() 함수 안에서 다시 hello()를 ㅗ출 
 
hello() # 종료 조건이 없어 Recursion Error 발생 

 

 

   2) 팩토리얼을 재귀 호출로 만들기 

       - 팩토리얼의 재귀호출형 표현

1! = 1 2!  = 2 × 1 = 2 × 1! 3! = 3 × (2 × 1) = 3 × 2! 4! = 4 × (3 × 2 × 1) = 4 × 3!  ... n! = n × (n - 1)!

 

즉, 

• 1 일단 n이 1 이하인지를 판단: 1 이하의 n은 종료 조건으로, 이때 결괏값은 1
• 2 n이 1 초과이면 n! = n × (n-1)!을 연산 ⇒ n × fact(n-1) 

              예) fact(4)를 호출하는 모습

fact(4) = 4 * fact(3)	fact(3) 호출
fact(3) = 3 * fact(2)	fact(2) 호출
fact(2) = 2 * fact(1)	fact(1) 호출
fact(1) = 종료 조건	1
fact(2) = fact(1) * 2	2
fact(3) = fact(2) *3	6
fact(4) = fact(3) * 4	24 (최종 결과)

 

# 구하는 방법2: 재귀호출로 팩토리얼 구현
 
def fact_rec(n):
    if n <= 1:
        return 1 # 재귀 호출에서 종료 조건의 결괏값부터 
    return n * fact(n-1)
 
fact_rec(5) # 120

 

 

3. 재귀 호출 팩토리얼의 알고리즘 계산 복잡도? O(n)

∵ n! = n * (n -1)! 이므로 곱셈이 n-1번 필요

    ex) 4! = 4 ׳ 3 ײ  2 ×¹  1 

 

 

<연습 문제>

1강의 1부터 n까지의 합 구하기를 재귀 호출로 만들기

      ※ 초기화하는 부분은 n<=1이 아니라 n ==0 임!!!!!!

# 1강의 1부터 n까지의 합 구하기를 재귀 호출로 만들기
 
def sums(n):
    if n == 0:
        return 0
    return n + sums(n-1)

오답노트: 초기화도 잘못했고 for문을 또 돌릴 뻔 했다! 재귀호출은 함수 자체에 for문이 필요가 없다. 

심지어 아래 코드는 'sum' 변수를 초기화해주는 과정도 없어 답도 제대로 안나옴 -_-;;

# 1강의 1부터 n까지의 합 구하기를 재귀 호출로 만들기
 
def sums2(n):
    if n  == 1:
        return 1
    for i in range(1, n+1):
        sum =  n + i
    return sum

 

 

 

2강의 숫자 n개 중 최댓값 찾기를 재귀 호출로 만들기: 모루겠소요

     정답지 코드는 아래와 같음

#2강의 숫자 n개 중 최댓값 찾기를 재귀 호출로 만들기 
# 정답지 코드
 
def find_max(a, n):
    if n ==1:
        return a[0]
    max_n_1 = find_max(a, n-1)
    if max_n_1 > a[n-1]:
        return max_n_1
    else:
        return a[n-1]
 
v = [17, 92, 18, 33, 58, 7, 33, 42]
print(find_max(v, len(v))) # 92

 

ㅇ

ㅇ