[05DFS/BFS] 5-3 재귀함수 (p130~p133)

[재귀 함수]

• 자기 자신을 다시 호출하는 함수를 의미함.

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

recursive_function()

 

이 함수를 실행하면, 아래와 같은 오류가 발생한다

내용은 즉, 재귀(Recursive)의 최대 깊이를 초과했다는 내용.

 

[재귀 함수의 종료 조건]

def recursive_function(i):
    #100번째 출력했을 때 종료되도록 종료 조건 명시
    if i == 100:
        return

    print(i, '번째 재귀 함수에서', i+1, '번째 재귀 함수를 호출합니다.')
    recursive_function(i+1)
    print(i, '번째 재귀 함수를 종료합니다.')

recursive_function(1)

 

• 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조로 수행됨.
• 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.
• 재귀함수의 대표적인 예제로는 팩토리얼(Factorial)이 있음.

[2가지 방식으로 구현한 팩토리얼 예제]

# 반복적으로 구현한 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
    return n * factorial_recursive(n - 1)

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

 

• 재귀 함수를 얻었을 때 장점은 코드가 간결해짐.
• 재귀 함수는 점화식의 개념이 사용되는데, 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것이다.
• 팩토리얼을 수학적 점화식으로 표현시

 

[재귀함수 사용시 주의사항]

• 무한루프에 빠지지 않도록 if문을 사용해서 종료 조건을 꼭 구현 해주어야 함.