재귀함수

재귀함수는 호출된 함수가 자기 자신을 다시 호출하는 것을 말합니다.

재귀함수를 구현하기 위해서 2가지를 정해야한다.

1. 언제 어떤 매개변수를 가지고 재귀를 호출할지.
2. 호출을 정지 시켜줄 base case

팩토리얼 재귀 코드 예시.

def factorial(n):
    # base case
    if n <= 0: # 1
        return 1
    return n*factorial(n-1)

if __name__ == "__main__":
    for i in range(1, 6):
        print(factorial(i))

함수를 호출하면 실행중이던 내용이 일시중지 되고 호출되는 함수가 스택에 쌓인다.

→ 재귀가 많아지면 스태 프레임 한계치에 도달해서 recuresion depth 에러가 발생할 수 있다.

⇒ 종료조건 base case를 무조건 명시해줘야한다.

모든 재귀함수는 재귀구조 없이 반복문 만으로 동일 동작을 수행하는 함수를 구현할 수 있다고합니다. 재귀를 잘 사용하면 코드가 간결해 질 수 있지만, 메모리와 시간적 측면에서 손해를 감수해야한다.