재귀

0. 재귀(Recursive Call)란

• 함수 안에서 함수 본인을 호출하는 것

# 기본 구조
def hello():
    print("Hello, World!")
    hello()

hello()

1. 종료 조건

• 재귀 함수는 최대 재귀 깊이가 정해져 있어, 그 깊이에 도달하면 RecursionErorr가 발생한다
• python의 경우 최대 재귀 깊이(max recursion depth)가 1,000임 (*왜 1000이지?)
• 따라서 재귀 함수 작성 시에는 종료 조건을 지정해야 한다.

def hello(count):
    if count == 0: return   #count가 0이면 hello 호출 안하고 멈춤
    
    print("Hello, world!")   #print
    count -= 1   #count를 1 감소시킴
    hello(count)   #감소된 count로 hello 호출

hello(5)

# k에서 시작, n까지 탐색 기본형
def function(k, n):
    if n == k:
    	return
    else:
    	function(k+1, n)
        
# 일반적인 형태1

2. 예제

# 팩토리얼
def factorial(num):
    if num > 1:
        return num * factorial(num-1)
    else:
        return num
    

# 회문 판별
def is_palindrome(word):
    if len(word) < 2:
        return True
    if word[0] != word[-1]:
        return False
    return is_palindrome(word[1:-1])

3. 시간복잡도, 공간복잡도

4. 언제 사용하는지?

참고
잔재미코딩
코딩도장