DFS/BFS 완전정복을 위한 재귀함수 기본이론

1. 재귀함수

 

DFS/BFS를 구현하려면 재귀함수도 이해하고 있어야한다

 

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

 

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

recursive_function()

 

이 코드를 실행하면 '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력한다

 

정의한 recursive_function()이 자기 자신을 계속해서 추가로 불러오기 때문이다

 

물론 어느정도 출력하다보면 오류 메시지를 출력한다

 

 

재귀의 최대 깊이를 초과했다는 애용으로 파이썬 인터프리터가 호출 횟수의 제한이 있기 때문이다

 

무한대로 재귀 호출을 할 수는 없으며 애초에 그런 문제 또한 출제될리는 없다

 

2. 재귀함수 예시

 

<유머>

 

어느 한 컴퓨터공학과 학생이 알고리즘 교수님을 찾아가 여쭈어보았다

 

학생: 재귀 함수가 무엇인가요?

 

교수: 잘 들어보게. 어느 한 컴퓨터 공학과 학생이 알고리즘 교수님을 찾아가 여쭈어보았다네.               학생: 재귀 함수가 무엇인가요?       교수: 잘 들어보게. 어느 한 컴퓨터공학과 학생이 알고리즘 교수님을 찾아가 여쭈어보았다네.                                학생: 재귀 함수가....

 

 

<프랙탈구조>

 

삼각형안에 또 다른 삼각형이 무한히 존재하는 시에르핀스키의 삼각형

 

프랙탈구조의 대표적인 그림으로 실제로 이런 이미지를 출력하는 프로그램을 작성할 때 재귀함수를 이용

 

 

3. 재귀함수 종료조건

 

재귀함수 문제를 사용할 때는 반드시 재귀 함수가 언제 끝날지 종료 조건을 명시해야한다.

 

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

 

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

    recursive_function(i+1)

    print(i, '번째 재귀 함수를 종료합니다.')

recursive_function(1)

 

위 함수는 재귀함수를 100번 호출하는 함수이다. 초반에 등장하는 if문이 종료 조건 역할을 수행한다

 

 

 

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다

 

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

 

컴퓨터의 구조 측면에서 보면 연속해서 호출되는 함수는 메인 메모리의 스택 공간에 적재되므로

 

재귀함수는 스택 자료구조와 같다는 말은 틀린 말이 아니다

 

위에서 보면 100번째 재귀함수까지 stack에 계속 쌓이고 100번째 재귀함수부터 처리해나가는 형태 1번째 재귀함수까지 처리해나가는 형태

 

 

스택 자료구조와 재귀 함수가 동일하기 때문에 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀함수를 이용해 구현할 수 있다

 

DFS가 대표적인 예시

 

 

 

4. 팩토리얼 문제

 

재귀함수를 이용하는 대표적인 예시

 

$n! = 1*2*3*...*(n-1)*n$

 

수학적으로 0!과 1!은 1로 같다는 성질을 이용하면 팩토리얼 함수는 n이 1이하가 되었을 때 함수를 종료하는 재귀 함수의 형태로 구현가능

 

반복적(iterative)으로 구한 방식과 재귀적(recursive)으로 구한 방식의 비교

 

def factorial_iterative(n):
    
    result = 1

    for i in range(1,n+1): #1부터 n까지의 수를 차례대로 곱한다
        
        result *= i
    
    return result


def factorial_recursive(n):
    
    if n <= 1: #n이 1 이하이면 1을 반환하고 종료
        
        return 1
    
    return n * factorial_recursive(n-1) #n! = n*(n-1)!
    
print('반복적으로 구현:',factorial_iterative(5))

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

반복적으로 구현: 120
재귀적으로 구현: 120

 

실행결과는 동일한데 반복문 대신에 재귀함수를 이용할 때 얻을 수 있는 장점은 무엇인가?

 

재귀함수의 코드가 더 간결하다.

 

이유는 팩토리얼의 점화식을 그대로 소스코드로 사용했기 때문이다.

 

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

 

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

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

 

일반적으로 우리는 점화식에서 종료조건을 찾을 수 있다

 

이 경우 'n이 0 혹은 1일때'가 종료조건이다.

 

팩토리얼은 n이 양의 정수일 때에만 유효하므로 n이 1이하이면 1을 반환할 수 있도록 재귀함수를 작성해야한다.

 

n이 1이하인 경우를 고려하지 않으면 재귀함수가 무한히 반복되어 결과를 출력하지 못할 것이다

 

또한 n의 값이 음수로 들어올때는 입력 오류로 오류 메시지를 띄우도록 코드를 작성할수도 있다

 

따라서 재귀함수 내에서 특정 조건일 때 더 이상 재귀적으로 함수를 호출하지 않고 종료하도록 if문을 이용하여 꼭 종료 조건을 구현해줘야한다.