[알고리즘] 재귀용법

<1>

재귀용법(recursive call, 재귀호출)

• 함수 안에서 동일한 함수를 호출하는 형태

• 여러 알고리즘 작성시 사용되므로, 익숙해져야 함

• 재귀 호출은 스택의 전형적인 예

• 파이썬에서 재귀 함수는 깊이가 1000회 이하가 되어야 함

복잡도

• 시간 복잡도 : O(n)
• 공간 복잡도 : O(n)

일반적인 형태

# 일반적인 형태1
def function(입력):
    if 입력 > 일정값: # 입력이 일정 값 이상이면
        return function(입력 - 1) # 입력보다 작은 값
    else:
        return 일정값, 입력값, 또는 특정값 # 재귀 호출 종료

# 일반적인 형태2
def function(입력):
    if 입력 <= 일정값:              # 입력이 일정 값보다 작으면
        return 일정값, 입력값, 또는 특정값              # 재귀 호출 종료
    function(입력보다 작은 값)
    return 결과값

<2>