재귀와 반복의 차이

 

코드 비교

 

다음 두개 코드의 차이점을 확인해보자

 

재귀

import sys
sys.setrecursionlimit(10000)
def solution(A):
    # Implement your solution here
    visited = [0 for _ in range(len(A))]
    def recursion(idx, num):
        if idx == -1 or visited[idx]==1:
            return num
        visited[idx] = 1
        return recursion(A[idx],num+1)
    return recursion(0,0)

 

반복

def solution(A):
    visited = [0 for _ in range(len(A))]
    idx = 0
    num = 0
    while idx != -1 and visited[idx] == 0:
        visited[idx] = 1
        idx = A[idx]
        num += 1
    return num

 

두 코드 모두 어렵지 않게 이해할 수 있다.

또한 두 개의 시간복잡도는 모두 O(N)이다. 하지만 반복은 통과하는 것을 재귀는 RuntimeError가 걸릴 수 있다.

 

그 이유는

재귀와 반복의 런타임 성능과 한계가 전혀 다르기 때문이다.

 

재귀는 호출 스택 사용

1. 재귀함수는 매 호출마다 콜 스택을 하나씩 소비한다.

• Python에서 함수 호출 시마다 로컬 변수, 리튼 주소, 스택 프레임이 스택에 쌓임
• 기본 스택 깊이 제한은 보통 약  1000번 (sys.recursionlimit()으로 조절 가능)
  • 이걸 넘으면 RecursionError: maximum recursion depth exceeded 발생

def f(x):
    if x == 0:
        return
    f(x - 1)

f(100000)을 호출하면 100000번의 함수 스택 프레임이 쌓이기 때문에 RecursionError가 나옴

 

2. 반복문은 콜 스택을 사용하지 않음

• 단일 루프안에서 idx 값만 갱신하며 로직을 수행하여 메모리 사용이 일정
• 어떤 크기의 입력이 와도 OS가 허용되는 범위 내에서만 CPU와 메모리를 쓰므로 터지지 않음