[알고리즘:파이썬] 04. 팩토리얼 구하기(재귀호출)

안녕하세요. 쏘피입니다. 오늘은 04. 팩토리얼 구하기 문제를 풀어보겠습니다.

 

 

 

---

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

---

풀이:

1) 입력: n

2) 출력: 1부터 n까지 연속한 숫자를 곱한 값

3) 파이썬으로 구현:

# 1부터 n까지 연속한 정수의 곱을 구하는 알고리즘을 만들어 보세요. def fact(n):     f = 1    #곱을 계산할 변수,초기값1     for i in range(1, n + 1): #1부터 n까지 반복         f = f*i     return f print(fact(10))

 

---

다음으로는 같은 문제를 재귀호출로 풀어보겠습니다.

잠깐! 재귀호출은 무엇일까요?

재귀호출: 어떤 함수 안에서 자기 자신을 부르는 것,

재귀호출 프로그램이 정상적으로 작동하려면 종료조건이 필요합니다. 

 

재귀 호출의 일반적 형태 def func(입력값):     if 입력 값이 충분히 작으면: #종료 조건           return 결괏값           .....    func(더 작은 입력 값)       #더 작은 값으로 자기 자신을 호출          .....    return 결괏값

 

---

그럼 재귀호출로 같은 문제를 풀어보겠습니다.

1) 입력: n

2) 출력: 1부터 n까지 연속한 숫자를 곱한 값

3) 재귀호출 알고리즘: n! = n * (n-1)!

4) 파이썬으로 구현:

# 1부터 n까지 연속한 정수의 곱을 구하는 알고리즘을 만들어 보세요. #재귀호출 개념 적용 def fact(n):     if n <=1: #1 이하는 종료조건         return 1     return n*fact(n-1) #fact(n-1)이 정의된 자기 자신 함수 fact()를 부른다. print(fact(5))

헷갈릴 수도 있는데요. fact(5)를 하면 5*fact(4)->5*4*fact(3)->5*4*3*fact(2)->5*4*3*2*fact(1) 즉 5*4*3*2*1이 됩니다.

 

---

알고리즘 분석

---

방식1: for 반복문->n! 구하려면 곱셈 n번 필요

방식2: 재귀호출 n! 구하려면 곱셈 n-1번 필요

그러므로 두 방식 모두 계산 복잡도는 O(n)

 

---

추가 연습문제

---

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

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

 

 

---

추가 연습문제 풀이

---

#4-1 1부터 n까지의 합 구하기를 재귀 호출로 만들어 보세요. def sum_n(n):     if n == 0: # 종료조건         return 0     return sum_n(n-1) + n print(sum_n(2))

#4-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]:           #a[n-1]:이번 차수에 나온 새로운 값과 비교         return max_n_1             #max_n_1: 이전에 나온 재귀함수 값     else:         return a[n - 1] v = [17, 92, 30] print(find_max(v, len(v)))

4-2는 이해가 어려워서 천천히 다시 봐봅니다.

17, 92, 30 이고 길이는 3

 

 

계산순서	계산	계산순서	계산
1	n이 3이므로 max_n_1 = find_max(v, 2) a[2]=30	6	92>30이므로 return max_n_1 즉 92 리턴
2	n이 2이므로 max_n_1 = find_max(v, 1) a[1]=92	5	17<92이므로 a[n-1]리턴 즉 92를 리턴
3	n이 2이므로 max_n_1 = find_max(v, 1) a[0]=17로 리턴이 되므로 max_n_1이 17	4	17

 

 

재귀호출은 충분히 작은 값부터 계산이 실질적으로 시작된다는 걸 생각하고 짜야겠네요.

---

문제 출처: 모두의 알고리즘 with 파이썬