자료구조, 재귀함수

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

재귀함수

자료구조에서 재귀란 함수의 실행 과정에서 자기 자신을 한번 이상 호출하는 함수를 의미한다.

def sum_n(n):
    if n == 1:
        return 1
    return sum_n(n-1) + n

이 함수를 실행시켜보면 sum_n(4) > sum(3) + 4 > sum(2) + 3 > sum(1) + 2 > 1으로 진행될 것이다.

수행시간은 T(n) = T(n-1) + C (C는 상수) > T(n-2) + C + C > T(n-3) + C + C + C ... > C*N(=T1~Tn)으로 시간복잡도는 O(n)임을 알 수 있다.

재귀함수의 주의점

1. 기본케이스(base case)를 반드시 만들어야한다.
2. recursive call이 반드시 있어야한다.

기본 케이스란 재귀 호출을 수행하지 않는 반환값을 의미한다. 위 코드에서 기본케이스는 if n == 1: return 1를 의미한다. 즉, 함수가 반복적으로 호출되었을때 제일 마지막 호출에서는 기본 케이스가 돌아야한다. 그렇지 않으면 코드는 무한반복으로 자기 자신을 호출하기 때문에 함수가 끝나지 않게된다. 파이썬에서의 while True를 떠올리면 이해가 쉽다.

그리고 재귀함수는 반드시 자기 자신을 한번 이상 호출해야한다. 위 코드에서는 return sum_n(n-1) + n에 해당한다.

이러한 재귀함수는 for,while문을 호출하지 않기에 좀 더 코드가 간결해진다는 장점은 존재하지만, 이러한 재귀호출이 많아지면 질수록 메모리의 효율은 떨어진다는 단점 또한 존재한다.