재귀 함수

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

• 고급 정렬 알고리즘에서 재귀 용법을 사용 한다.
• 함수 안에서 동일한 함수를 사용

예제

def factorial(num):
    if num > 1 :
        return num * factorial(num-1)
    else:
        return num

시간 / 공간 복잡도 모두 O(n-1)이므로, 둘다 O(n)이 된다.

def function(입력):
    if 입력 > 일정값:
        return function(입력-1)
    else:
        return 일정값

재귀 호출은 내부적으로 스택처럼 관리 된다.

파이썬에서 재귀 호출의 최대 깊이는 1000회이다. (즉, 스택 공간이 1000개)

def palindrome(data):
    pal_data = data[::-1]
    if data == pal_data:
        return True
    else:
        return False

재귀 방식이 아닌 일반 회문

def palindrome(data):
    if len(data) <= 1:
        return True
    if data[0] == data[-1]:
        return palindrome(data[1:-1])
    else:
        return False

재귀 방식을 사용한 회문