Recursive

Recursive(재귀호출)

• 개념: 함수 안에서 동일한 함수를 여러번 호출하는 형태

• 특징

  • 재귀호출은 스택의 대표적인 예시(만약 조건을 만족했다면 그 순간부터 pop)
  • 문제 내에서는 조금씩 줄여나가는 형태
  • 결국 똑같은 식이 반복된다면 재귀를 의심
  • 파이썬은 1000회이하까지만 작동(파이썬 스택의 최대공간은 약 1000이라고 볼 수 있음)

• 코드

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

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

• 시간복잡도 & 공간복잡도: 둘 다 O(n) _ n-1번의 반복문을 호출하는 형태