Python/알고리즘 연습
4. 팩토리얼 구하기 - 재귀 호출의 등장
김아다만티움
2024. 7. 12. 15:25
 |
* 책: 모두의 알고리즘 with 파이썬 |
1부터 n까지 연속한 정수의 곱을 구하는 알고리즘을 만들어 보세요. (=팩토리얼 구하기)
1. 팩토리얼을 구하는 알고리즘 ①
1부터 n까지의 합을 구하는 코드를 변형하여 만들기 가능
|
1
2
3
4
5
6
7
8
9
|
# 구하는 방법1: 1부터 n까지의 합을 구하던 코드 변형
def fact(n):
m = 1
for i in range(1, n+1):
m = m * i
return m
fact(5) # 120
|
cs |
2. 팩토리얼을 구하는 알고리즘 ②: '재귀호출' 사용
1) 재귀호출(recursion) 이란?: 함수 안에서 자기 자신을 부르는 것
- 재귀 호출 시 반드시 끊어주는 "종료 조건"이 있어야 함
- 재귀 호출 함수는 계산 결과 리턴 시 'return 종료 조건 결괏값' 부터 보여줌
|
1
2
3
4
5
6
7
|
# hello()를 끊임없이 부르는 함수
def hello():
print("Hello, World!")
hello() # hello() 함수 안에서 다시 hello()를 ㅗ출
hello() # 종료 조건이 없어 Recursion Error 발생
|
cs |
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 (최종 결과) |
|
1
2
3
4
5
6
7
8
|
# 구하는 방법2: 재귀호출로 팩토리얼 구현
def fact_rec(n):
if n <= 1:
return 1 # 재귀 호출에서 종료 조건의 결괏값부터
return n * fact(n-1)
fact_rec(5) # 120
|
cs |
3. 재귀 호출 팩토리얼의 알고리즘 계산 복잡도? O(n)
∵ n! = n * (n -1)! 이므로 곱셈이 n-1번 필요
ex) 4! = 4 ׳ 3 ײ 2 ׹ 1
<연습 문제>
1강의 1부터 n까지의 합 구하기를 재귀 호출로 만들기
※ 초기화하는 부분은 n<=1이 아니라 n ==0 임!!!!!!
|
1
2
3
4
5
6
|
# 1강의 1부터 n까지의 합 구하기를 재귀 호출로 만들기
def sums(n):
if n == 0:
return 0
return n + sums(n-1)
|
cs |
오답노트: 초기화도 잘못했고 for문을 또 돌릴 뻔 했다! 재귀호출은 함수 자체에 for문이 필요가 없다.
심지어 아래 코드는 'sum' 변수를 초기화해주는 과정도 없어 답도 제대로 안나옴 -_-;;
|
1
2
3
4
5
6
7
8
|
# 1강의 1부터 n까지의 합 구하기를 재귀 호출로 만들기
def sums2(n):
if n == 1:
return 1
for i in range(1, n+1):
sum = n + i
return sum
|
cs |
2강의 숫자 n개 중 최댓값 찾기를 재귀 호출로 만들기: 모루겠소요
정답지 코드는 아래와 같음
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#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
|
cs |
ㅇ
ㅇ