꼭 필요한 자료구조 기초 - 재귀함수

📌재귀함수

자기 자신을 다시 호출하는 함수

DFS와 BFS를 구현하려면 재귀함수도 이해해야 함

 

📌재귀함수 코드

def recursive_function():
    print("재귀함수를 호출합니다.")
    recursive_function()


recursive_function()

 

📌재귀함수의 종료 조건

재귀함수의 종료 조건을 꼭 명시해야 함

자칫 종료 조건을 명시하지 않으면 함수가 무한 호출 될 수 있음

 

📌코드

def recursive_function(i):
    # 100번째 출력했을 때 종료되도록 종료 조건 명시
    if i == 100:
        return
    print(i, "번째 재귀 함수에서", i + 1, "번째 재귀 함수를 호출합니다.")
    recursive_function(i + 1)
    print(i, "번째 재귀 함수를 종료합니다.")


recursive_function(1)

 

재귀 함수는 내부적으로 스택 자료구조와 동일

함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료

 

📌팩토리얼 예제

# 반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n + 1):
        result *= i
    return result


# 재귀적으로 구현한 n!
def factorial_recursive(n):
    if n <= 1:
        return 1
    # n!=n*(n-1)을 그대로 코드로 작성
    return n * factorial_iterative(n - 1)


print("반복적으로 구현:", factorial_iterative(5))
print("재귀적으로 구현:", factorial_recursive(5))

 

📌재귀함수 장점

코드가 더 간결

재귀함수가 수학의 점화식을 그대로 소스코드로 옮겼기 때문

 

수학의 점화식: 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현

 

1. n이 0 혹은 1일 때: factorial(n)=1

2. n이 1보다 클 때: factorial(n)=n*factorial(n-1)

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬