재귀의 이해
재귀함수
스스로를 호출하는 함수
| DFS(깊이 우선 탐색) | BFS(너비 우선 탐색) |
| 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 경로의 특징을 가진다 |
현재 정점에 연결된 가까운 점들부터 탐색 |
| 스택 또는 재귀함수로 구현 | 큐를 이용해서 구현 |
return 값이 없는 재귀함수
def recursion(n):
if n < 5:
recursion(n + 1)
recursion(1)
# 1
# 2
# 3
# 4
return 값이 있는 재귀함수
def recursion(n):
if n <= 0:
return 0
return n + recursion(n - 1)
print(recursion(4)) # 10
모든 재귀함수는 반복문으로 구현이 가능하다
>>> 코드가 훨씬 짧기 때문에 재귀함수 사용
종료 조건이 중요하다
>>> 끝도 없이 호출되서는 안 됨. 언젠가는 실행이 멈춰야 함
RecursionError: maximum recursion depth exceeded while calling a Python object
최대 재귀 깊이(maximum recursion depth)
재귀함수를 최대로 호출할 수 있는 횟수 파악
print(sys.getrecursionlimit())
재귀 문제 유형
1. 문제 푸는 전체 과정을 펼쳐 생각해 보았을 때
>>> 문제 풀이 과정의 일부분이 문제를 푸는 전체 과정과 유사함
2. 문제 풀이 과정에서 비슷한 논리가 꼬리에 꼬리를 무는 형태로 이루어져 있음
팩토리얼(!)
어떤 수보다 작거나 같은 모든 양의 정수를 곱한 값
def factorial(n):
if n == 0:
return 1
return n * factorial(n-1)
print(factorial(16))
피보나치 수열
첫째 항이 0, 둘째 항이 1
그 뒤의 모든 항은 바로 앞 두 항의 합인 수열
def fibo(n):
if n == 1:
return 0
elif n == 2:
return 1
return fibo(n-1) + fibo(n-2)
print(fibo(12)) # 89
과제
파스칼의 삼각형(Pascal's triangle)
8번째 줄을 리스트로 출력하는 함수 만들기
1. 첫번째 줄에는 1을 쓴다
2. n번째 줄(n >= 2) 줄을 만들 때 n-1번째 줄의 왼쪽 숫자와 오른쪽 숫자를 더한다
n-1번째 줄의 왼쪽 숫아 혹은 오른쪽 숫자 중 하나가 없을 경우 존재하는 수만 더한다
def pas(n):
if n == 1:
return [1]
else:
return [1] + [(pas(n-1)[i])+(pas(n-1)[i+1]) for i in range(n-2)] + [1]
print(pas(8)) # [1, 7, 21, 35, 35, 21, 7, 1]
클래스 심화
메서드 오버라이딩(Method Overriding)
파생 클래스에서 상위 클래스의 메서드를 재정의하는 것
이름은 같지만 다른 기능을 수행하도록 재정의
1. 모델 클래스 메서드 오버라이딩
from django.db import models
class MyModel(models.Model):
name = models.CharField(max_length=100)
# save 메서드를 오버라이딩하여 저장하기 전 특정 작업 수행
def save(self, *args, **kwargs):
self.name = self.name.upper() # name 속성의 값을 대문자로 변환
super(MyModel, self).save(*args, **kwargs) # 저장
2. 폼 클래스 메서드 오버라이딩
from django.db import forms
class MyForm(forms.Form):
name = forms.CharField(max_length=100)
# clean_name 메서드를 오버라이딩하여 입력값을 검증하거나 처리하는 등의 작업 수행
def clean_name(self):
name = self.clean_data['name']
return name.capitalize() # name 필드 값의 첫 글자를 대문자로 변환
3. 뷰 함수 메서드 오버라이딩
from django.views.generic import TemplateView
class MyView(TemplateView):
template_name = 'my_template.html'
# dispatch 메서드를 오버라이딩
def dispatch(self, request, *args, **kwargs):
# 요청 처리 전 특정 작업 수행
result = super(MyView, self).dispatch(request, *args, **kwargs)
# 요청 처리 후 특정 작업 수행
return result
추상 클래스(Abstract Class)
- 상속하여 하위 클래스에서 구현해야 하는 클래스
- 상속받는 클래스에서 반드시 구현해야 함
- 인터페이스만 정의해 줌
- 인스턴스를 생성할 수 없는 클래스
serializer를 사용하는 이유
- 직렬화
- 데이터 검증
serializer의 validate
필드의 유효성 검사 → 커스텀 validate
is_valid
serializer.is_valid(raise_exception=True)
serializer.save()
def save(self, **kwargs):
pass
raise_exception=True를 통해 is_valid 체크에서 에러가 나면
ValidationError를 raise 하여 HTTP 400 Bad Request 응답을 리턴
- self.instance 값이 있을 때 : update()를 통해서 저장
- self.instance 값이 없을 때 : create()를 통해서 저장
def crate(self, validated_data)
password = validated_data.pop("password")
user = User(**validated_data)
user.set_password(password)
user.save()
다음 주 예고
- 다형성
- 데코레이터 (DRF View)