[TIL] 230426 재귀함수 / 클래스상속 추상클래스

<재귀함수>

스스로 호출하는 함수 
깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS) *참고링크
트리 ← 중위.전위.후위 순회 → 재귀

리턴값 無 재귀함수와 리턴값 有 재귀함수도있지만, 코딩테스트에서는 리턴값 有 재귀함수를 자주 활용하여 푼다.

<재귀함수를 쓰는 이유?!>

-반복문 중복보다 효율적일 경우가 있다!
-유의할 점: 종료 조건. 끝도 없이 호출되어서는 안된다. 실행을 멈출 종료 시점을 알아야한다.

RuntimeError

#최대 재귀 깊이 (maximum recursion depth): 재귀함수를 최대로 호출할 수 있는 횟수 파악
print(sys.getrecursionlimit())

<재귀를 써야한다?! 판단기준>

1. 문제 푸는 전체과정을 펼처 생각해보았을 때
2. 문제 풀이 과정의 일부분이 문제를 푸는 전체 과정과 유사하다
→ 즉, 문제 풀이 과정에서 비슷한 논리가 꼬리에 꼬리를 무는 형태로 이루어져 있음! 프렉탈구조!

재귀함수 예시 - 팩토리

# 재귀로 풀어보기(1) 팩토리얼
def factorial(n):
    if n <= 1 :
        return 1
    return n * factorial(n-1)
    
print(factorial(5))
print(factorial(6))
print(factorial(7))
print(factorial(8))
print(factorial(9))
print(factorial(10))
    
'''
120
720
5040
40320
3628803628800
'''

재귀함수 예시 - 피보나치

# 재귀로 풀어보기(2) 피보나치
def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    return fib(n-1)+fib(n-2)

print(fib(5))
print(fib(6))
print(fib(7))
print(fib(8))
print(fib(9))
print(fib(10))

'''
5
8
13
21
34
55
'''

재귀함수 예시 - 파스칼의 삼각형

import os
os.system("cls")

# 파스칼 삼각형 만들기!
'''
pt(1) = [ 1 ] 
pt(2) = [ 0+pt(1)[0], pt(1)[0]+0 ]
pt(3) = [ 0+pt(2)[0], pt(2)[0]+pt(2)[1] ,pt(2)[1]+0 ]
pt(4) = [ 0+pt(3)[0], pt(3)[0]+pt(3)[1], pt(3)[1]+pt(3)[2] ,pt(3)[2]+0 ]
...
pt(n) = [ 0+pt(n-1)[0], pt(n-1)[0]+pt(n-1)[1], ... , pt(n-1)[n-3]+pt(n-1)[n-2], pt(n-1)[n-2]+0 ] 
...

'''

def pt(n):
    result = [1]
    if n == 1:
        return [1]
    elif n == 2:
        return [1 , 1]
    elif n > 2:
        for i in range(len(pt(n-1))-1):
            result.append(pt(n-1)[i]+pt(n-1)[i+1])
        result.append(1)
        return result
    else:
        return print("[자연수를 입력하세요]")
        
print(pt(1))
print(pt(2))
print(pt(3))
print(pt(4))
print(pt(5))
print(pt(6))
print(pt(7))
print(pt(8))

'''
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
'''

<클래스 심화>

메서드 오버라이딩(Method Overriding)
추상클래스

<메서드 오버라이딩(Method Overriding)>

파생 클래스에서 상위 클래스의 메서드를 재정의하는 것!
내 입맛대로 커스텀!

Django에서의 메서드 오버라이딩
1. 모델 클래스의 메서드 오버라이딩
ex) save메서드를 오버라이딩하여 저장 시 기능을 추가한다.

2. 폼 클래스의 메서드 오버라이딩
ex) clean메서드를 오버라이딩하여 입력값을 검증하거나 처리하는 등의 작업을 수행

3. 뷰 함수의 메서드 오버라이딩
ex) dispatch 메서드를 오버라이딩하여 요청 전 후 특정작업수행!

<추상클래스(Abstract Class)>

-상속을 위한 뼈대만 만들어 둔 클래스
-추상클래스 만으로는 인스턴스를 생성할 수 없다.
-상속받는 각 클래스마다 커스텀이 필요할 경우 추상클래스로 필요 메서드를 미리 만들어둔다!
즉, 커스텀을 위한 뼈대를 구축한 클래스가 추상클래스 이다.