재귀 함수 Recursive Fuction

재귀 함수란

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

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

recursive_function()


#출력
재귀 함수를 호출합니다
재귀 함수를 호출합니다
재귀 함수를 호출합니다
재귀 함수를 호출합니다
...

RecursionError : maximum recursion depth exceeded while pickling an object

위와 같이 실행하면 문자열을 무한히 출력하다가 재귀의 최대 깊이를 초과했다는 메시지가 뜰 것이다.

재귀 함수는 프랙털(Fractal) 구조와 흡사하다.

위 그림은 시에르핀스키(Sierpinski)의 삼각형이다. 삼각형 안에 또 다른 삼각형이 무한히 존재하는 이 그림은 프랙털 구조의 대표적인 그림으로 실제로 이러한 프랙털 이미지를 출력하는 프로그램을 작성할 때에도 재귀 함수를 이용한다.

재귀 함수의 종료 조건

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다.
예를 들어 다음은 재귀 함수를 100번 호출하도록 작성한 코드이다. 재귀 함수 초반에 등장하는 if문이 종료 조건 역할을 수행한다.

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


recursive_function(1)

컴퓨터의 구조 측면에서 보자면 연속해서 호출되는 함수는 메인 메모리의 스택 공간에 적재되므로 재귀 함수의 수행은 스택 자료구조를 이용한다.
함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.

#반복적으로 구현한 n!
def factorial_iterative(n):
    result = 1
    for i in range(1, n+1):
        result *= 1
    return result

def factorial_recursive(n):
    if n<=1:
        return 1
    return n*factorial_recursive(n-1)

#소스코드를 반복적(iterative)으로 구현한다는 말은 반복문을 이용한다는 의미이며, 흔히 재귀적(Recursive)로 구현한다는 말과 대비되는 의미로 사용

실행 결과는 동일하다.
위 코드와 비교했을 때 재귀 함수가 더 간결한 것을 알 수 있다. 재귀함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문이다.
수학에서 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미한다.
(피보나치 수열처럼 재귀식이 반복에 비해 비효율적인 경우가 있으니 참고하자)