[TIL] 97. 재귀(Recursion)

키워드

• 수학적 사고
• 재호출 로직
• 재귀 호출 -> 스택의 개념(함수 내부)
• 베이스 케이스
• 추가 조건

재귀(Recursion)

• 자기 자신을 재호출 하는 것, 종료 조건이 충족될 때까지 반복 수행
• 문제를 해결하는 재호출 로직 기억(추가 조건)
• 재귀함수를 멈추는 base case(반복을 중지하는 조건)
• 하위 문제를 쉽게 해결할 수 있을 때까지 더 작은 하위 문제로 나누는 것

재귀 예시

def sum_list(items):
    if len(items) == 1:
        return items[0] # base case -> 재귀함수 종료 
    else:
        return items[0] + sum_list(items[1:]) # 추가 조건 -> 재호출 로직

[재귀] 조건

1. base case(기본 케이스)가 있어야 한다.
2. 추가 조건을 두어 기본 케이스와의 차이를 확인한다.
3. 반드시 자기 자신을 호출한다.(추가 조건에서 재호출)

[재귀] 함수의 콜스택

• 재귀 호출은 스택의 개념이 적용되어 함수 내부는 마치 스택처럼 후입선출(LIFO)로 관리된다.
  (눈 뜨고 잘 봐야됨)

예시)

# 파이썬 함수 콜스택 예시
def multi_table_2(n):

    if n == 0:
        print('구구단 2단')
    else:
        multi_table_2(n-1) # 이 부분에서 함수가 스택처럼 쌓임(즉, multi_table_2(9)가 제일 아래에 쌓임)
        print(f"2 * {n} = {2 * n}")

multi_table_2(9)

예시 출력)

구구단 2단
2 * 1 = 2
2 * 2 = 4
2 * 3 = 6
2 * 4 = 8
2 * 5 = 10
2 * 6 = 12
2 * 7 = 14
2 * 8 = 16
2 * 9 = 18

[재귀] 제한

• 재귀를 사용하면 스택 메모리에 계속 함수가 쌓이게 되는데 파이썬에서는 이 메모리를 1000스택을 기본으로 하고 있다.
  이 기본 1000을 넘어가면 에러가 발생, -> 이게 그 유명한 '스택오버플로우' 사이트 이름의 유래

import sys
sys.setrecursionlimit(3500)

• 위의 코드를 통해 재귀 스택을 더 늘려줄 수 있음(위의 경우 3500까지 늘려준 예시)