[codeit] 재귀 함수 (Recursive Function)

재귀적으로 푼다는 것은,

문제를 쪼개서 더욱 더 작은 문제로 푸는 것이라고 생각한다.

 

 

재귀 = 반복문, 이런식으로 접근하는 것이 가능하다.

 

하지만 재귀에는 치명적인 문제가 있는데,

 

함수를 재귀적으로 너무 많이 호출하게 되면 call stack이 너무 많이 쌓이게 되어 stackOverflow 에러가 발생하게 된다.

 

 

 

재귀 함수에는 기본적으로 recursive case 와  base case가 있다.

 

• Recursive case : 현 문제가 너무 커서, 같은 형태의 더 작은 부분 문제를 재귀적으로 푸는 경우
• Base case : 이미 문제가 충분히 작아서, 더 작은 부분 문제로 나누지 않고 답을 알 수 있는 경우

 

 

재귀적으로 다가가 본 피보나치 수열

def fib(n):
    # base case
    if n < 3:
        return 1
    
    # recursive case
    return fib(n - 1) + fib(n - 2)
    

 

 

시간 복잡도의 측면에서 다가가보자면,

 

매 호출마다 fib 함수가 재귀적으로 두 번 더 호출되고 이것이 base case 까지 진행됩니다.

 

이 단계의 개수는 n과 비례합니다. 문제는 약 n번 두배 씩 커지게 된다.

 

그러므로 시간복잡도는 O(2^n) 이다.

 

 

 

각 자릿수 합에 대한 재귀 함수

def sum_digits(n):
    # base case
    if n < 10:
        return n

    # recursive case
    return n % 10 + sum_digits(n // 10)

 

시간 복잡도 측면에서 다가가보면,

 

int n의 자릿수의 길이를 d라고 표현하면, ex) n = 15432 일시, d = 5이다.

 

sum_digits의 n은 매 호출마다 1/10으로 줄어들기 때문에 d 번 호출 된다.

 

그러므로 sum_digits의 시간복잡도는 O(d) 이다.

 

 

리스트 뒤집기 - 재귀함수 버전

# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
    # base case
    if len(some_list) == 0 or len(some_list) == 1:
        return some_list

    # recursive case
    return some_list[-1:] + flip(some_list[:-1])

# 테스트
some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
some_list = flip(some_list)
print(some_list)

 

base case 는 그냥 O(1) 이고,

 

rerrcursive case 는 재귀적 부분을 제외했을 시,

 

some_list[ -1 : ]는 O(1) 이고 some_list[ : -1 ]은 O(n - 1)이므로 둘을 더 해 O(n) 나온다.

 

flip함수 자체의 시간복잡도는 리스트의 길이를 -1씩 줄여가며 진행하므로 리스트의 길이가 n 일시 n번 진행되므로

 

O(n) 이다.

 

그러므로 재귀적으로 n번 실행되고 각 호출이 O(n) 이기 때문에 최종 시각복잡도는 O(n^2) 이다.