재귀 함수 (2) - 재귀 함수의 종료 조건

앞의 게시물에서도 이야기 했듯이 재귀 함수에는 반드시 적절한 종료 조건이 존재해야 한다. 따라서 문제를 해석하고 알고리즘을 구현할 때 언제 어떻게 재귀 호출을 종료하고 return 해야 하는지를 생각해야 할 것이다. 종료 조건을 추가한 재귀 함수에 대한 예시 소스코드이다.

def recursive(i):
    if i == 100 :
        return
    print(i,"번째 재귀함수가 ",i+1,"번째 재귀함수 호출")
    recursive(i+1)
    print(i,"번째 재귀함수 종료")

recursive(1)

이전의 예시와 유사하지만 recursive 함수에서 ' i '라는 매개변수가 존재한다. 먼저 가장 마지막 줄인 recursive(1)의 구문으로 재귀 함수가 매개변수 i에 1의 값을 갖고 호출된다. if 조건문에서 i가 100인지를 검사하고 "1번째 재귀함수가 2번째 재귀함수 호출" 이라는 메시지를 출력한다. 이후 recursive(2)가 호출 될 것이다. 이러한 과정이 i가 100일때까지 반복되며 i 가 100인 경우에는 리턴(return)하게 된다. 리턴 이후에는 호출 구문의 아랫줄이 실행되는데 이는 "99번째 재귀함수 종료" 라는 메시지 일 것이다. 이후 99부터 1까지 종료 메시지를 출력하고 프로그램을 종료한다.

이를 통해 확인할 수 있듯이 재귀 함수는 스택의 자료구조를 사용한다. 즉, LIFO의 방식을 보인다는 것이다. 왜냐하면 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내고 리턴해야 그 이전의 함수가 종료되기 때문이다.

따라서 스택을 활용해야 하는 알고리즘은 재귀 함수를 통해서 쉽게 구현할 수 있는 것이다.