재귀 함수

재귀 함수 (recursive function)

• 자기 자신을 호출하는 함수를 의미
• 무한한 호출을 목표로 하는 것이 아니며, 알고리즘 설계 및 구현에서 유용하게 활용
  • 알고리즘 중 재귀 함수로 로직을 표현하기 쉬운 경우가 있음(ex - 점화식)
  • 변수의 사용이 줄어들며, 코드 가독성이 높아질 수 있음
• 1개 이상의 base case(종료되는 상황)가 존재하고, 수렴하도록 작성
  • 같은 문제를 다른 input 값을 통해서 해결과는 과정
    • 하나의 큰 문제를 해결하기 위해 작은 문제로 좁히고, 작은 문제의 답을 이용하여 해결
  • 작은 문제는 base case에 도달하여 재귀 함수가 끝날 수 있도록 함

- 예시 

• 팩토리얼 재귀

# 팩토리얼 계산을 위한 코드를 작성하라

# 반복문 사용
def fact(n):
    result = 1
    while n > 1:
        result *= n
        n -= 1       
    return result
    
    print(fact(5))
        
# 재귀 사용
def factorial(n):
    if n == 1: # basecase 에 해당한다
        return 1
    return n * factorial(n-1)

print(factorial(5))

 

• 피보나치 재귀

# 반복문 사용
def fib_loop(n):
    if n < 2:
        return n
    
    a, b = 0, 1
    
    for i in range(n-1):
        a, b = b, a+b
    return b

# 재귀 사용
def fib(n):
    # base case
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

- 주의사항

• 재귀 함수는 base case에 도달할 때까지 함수를 호출함
• 메모리 스택이 넘치게 되면(stack overflow) 프로그램이 동작하지 않게 됨
• 파이썬에서는 최대 재취 깊이(maximum recursion depth)가 1,000번으로, 호출 횟수가 이를 넘어가게 되면 Recursion Error가 발생

def test():
	test()
    
test()

# RecursionError 발생!