1. 재귀함수
1) 팩토리얼 factorial
| n ! = n * (n-1) * (n-2) * ... * 1 |
👾 이러한 팩토리얼을 구하는 방법은 2가지로 구분
a. 반복문 사용
b. 재귀 함수 사용
A. 반복문으로 팩토리얼 구하기
def factorial(n):
output = 1
for i in range(1, n+1):
output *= i
return output
print("1!:", factorial(1))
print("2!:", factorial(2))
print("3!:", factorial(3))
print("4!:", factorial(4))
'''
1!: 1
2!: 2
3!: 6
4!: 24
'''
B. 재귀 함수로 팩토리얼 구하기
- 재귀 recursion 란 '자기 자신을 호출하는 것'을 의미
f(4) = 4 * f(3)
= 4 * 3 * f(2)
= 4 * 3 * 2 * f(1) * f(0)
= 4 * 3 * 2 * 1 * 1def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
print("1!:", factorial(1))
print("2!:", factorial(2))
print("3!:", factorial(3))
print("4!:", factorial(4))
2. 피보나치 수열 Fibonacci numbers
👩🏻💻 피보나치 수를 처음 연구한 것은 레오나르도 피오나치로 토끼 수의 증가에 대해서 이야기하면서 이 수에 대해 언급했다
📌 n 번째 달의 토끼 수는
- 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다.
- 두 달 이상이 된 토끼는 번식 가능하다.
- 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
- 토끼는 죽지 않는다.
📌 1번째 수열 = 1
2번째 수열 = 1
n번째 수열 = (n-1)번째 수열 + (n-2)번째 수열
def fibonacci(n):
if n == 1:
return 1
if n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print("fibonnaci(1):", fibonacci(1))
print("fibonnaci(2):", fibonacci(2))
print("fibonnaci(3):", fibonacci(3))
print("fibonnaci(4):", fibonacci(4))
'''
fibonnaci(1): 1
fibonnaci(2): 1
fibonnaci(3): 2
fibonnaci(4): 3
'''
count = 0
def fibonacci(n):
print("fibonacci({})를 구합니다.".format(n))
global count
count += 1
if n == 1:
return 1
if n == 2:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
fibonacci(10)
print("---")
print("fibonacci(10) 계산에 활용된 덧셈 횟수는 {}번입니다.".format(count))
'''
fibonacci(10)를 구합니다.
fibonacci(9)를 구합니다.
...생략...
fibonacci(1)를 구합니다.
fibonacci(2)를 구합니다.
---
fibonacci(10) 계산에 활용된 덧셈 횟수는 109번입니다.
'''
💡 위와 같이 덧셈 횟수가 기하급수적으로 늘어나는 이유
👾 다음과 같은 형태의 그림을 트리 tree 라고 한다.
👾 트리에 있는 각각의 지점을 노드 node, 마지막 단계의 노드를 리프 leaf
➡️ 트리 내부에 있는 각각의 노드 값을 계산하려면 덧셈을 한 번씩 해야 함
➡️ 한 번 구한 값은 그것으로 계산이 끝나는 게 아니라,
한 번 구했던 값이라도 처음부터 다시 계산해야 함
➡️ 이 때문에 계산 횟수가 기하급수적으로 늘어나는 것
💡 위의 예제에서 global count를 쓰는 이유
- 파이썬은 함수 내부에서 함수 외부에 있는 변수를 참조하지 못한다.
- 함수 내부에서 함수 외부에 있는 변수라는 것을 설명하려면 다음과 같은 구문을 사용해야 UnboundLocalError가 발생하지 않는다.
global 변수 이름
3. 메모화
👩🏻💻 한 번 계산한 값을 저장해 놓은 후, 이후에 다시 계산하지 않고 저장된 값을 활용하는 기술
# 메모 변수 생성
dic = {
1: 1,
2: 1
}
def fibonacci(n):
if n in dic:
# 메모가 되어 있으면 메모된 값을 리턴
return dic[n]
else:
# 메모가 되어 있지 않으면 값을 구함
output = fibonacci(n-1) + fibonacci(n-2)
dic[n] = output
return output
# 함수 호출
print("fibonnaci(10):", fibonacci(10))
print("fibonnaci(20):", fibonacci(20))
print("fibonnaci(30):", fibonacci(30))
print("fibonnaci(40):", fibonacci(40))
👾 딕셔너리를 사용해서 한 번 계산한 값을 저장, 이를 메모한다고 표현
👾 딕셔너리에 값이 메모되어 있으면 처리를 수행하지 않고 곧바로 메모된 값을 돌려주면서 코드 속도를 빠르게 만든다.
4. 리스트 평탄화
👩🏻💻 중첩된 리스트가 있을 때 중첩을 모두 제거하고 풀어서 1차원 리스트로 만드는 것을 의미
def flatten(data):
output = []
for item in data:
if type(item) == list:
output += flatten(item)
else:
output.append(item)
return output
example = [[1,2,3], [4,[5,6]], 7, [8, 9]]
print(flatten(example))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
⚡️ append() 함수는 매개변수 하나를 리스트의 마지막 요소로 추가
➡️ append(리스트_자료형) 형태로 리스트를 전달하면 리스트 전체가 하나의 요소로서 추가됨
⚡️ += 연산자는 오른쪽에 있는 '리스트의 요소'를 하나하나 리스트에 추가
[ 내용 참고 : 책 '혼자 공부하는 파이썬']
'Programming Language > Python' 카테고리의 다른 글
| [Python] 모듈(module), math, random, datetime, time (0) | 2024.03.03 |
|---|---|
| [Python] 튜플(tuple)과 람다(lambda), 제너레이터(generator) (0) | 2024.03.02 |
| [Python] 함수(function), 인수와 매개변수, 리턴(return) (0) | 2024.03.02 |
| [Python] 내장 함수 (built-in function) - 문자/숫자/시퀀스, 리스트 내포, 이터레이터 (iterator) (0) | 2024.03.02 |
| [Python] while 반복문, break/continue 키워드 (0) | 2024.03.02 |
