4월8일 - 재귀 vs 반복문

문제

https://school.programmers.co.kr/learn/courses/30/lessons/132267

프로그래머스

 

풀이 1

def solution(a, b, n):
    def fn(n, coke):
        if n < a:
            return coke
        output = n//a*b
        coke += output
        return fn(output + n%a, coke)
    return fn(n, 0)

 

다른 건 다 정답이고 테스트 12에서만 런타임 에러가 뜨는 걸 보니 

시간초과인듯 한데 

도무지 알 수 없어서 질문 탭에서 힌트를 참고한 결과, 

파이썬에서는 'maximum recursion depth exceeded' 에러가 발생해 프로그램이 중단될 수 있다고 한다.

 

그래서 반복문으로 풀어봤다.

 

풀이 2

def solution(a, b, n):
    coke = 0
    while n >= a:
        new = n // a * b
        coke += new
        empty = n % a
        n = new + empty
    return coke

깔끔하게 올 클리어

 

재귀 vs 반복문

문득, 재귀를 배우고 나서부턴 재귀를 쓸 수 있을 것 같은 상황이면 

항상 재귀를 써왔던 것 같다.

재귀의 장단점도 모른채

그래서 한번 재귀와 반복문의 장단점을 비교해보았다.

 

재귀의 장단점은 다음과 같다.

 

장점

• 반복문보다 간결하게 표현할 수 있어서 가독성이 좋다.
• 특정 조건 만족 시 함수를 중단하고 이전 단계로 되돌아 갈 수 있다.

단점

• 반복문에 비해 함수 호출 비용이 높다.
• 코드가 실행될 때마다 호출 스택을 생성하고 제거하는 오버헤드가 발생한다.
• 함수 호출 스택을 사용하므로, 함수 호출의 깊이가 깊어지면 스택 오버플로우가 발생할 수 있다.

 

정리

정리하자면 재귀는 반복문보다 기능적으로 효율이 좋은게 없다고 볼 수 있다.

다만, 알고리즘에서 더욱 직관적으로 코드를 작성할 수 있다는 점에서

핵심 아이디어를 더욱 명확하게 표현할 수 있다는 게 큰 장점으로 작용한다.

 

키워드

오버헤드(overhead)

오버헤드란 어떤 작업을 수행하기 위해 추가로 필요한 부분을 말한다.

주로 프로그램 실행에 필요한 추가적인 시간, 메모리, CPU 자원 등을 의미하는데

이러한 오버헤드는 프로그램 실행의 효율성을 떨어뜨릴 수 있으며, 특히 실행 속도가 중요한 프로그램에서는 큰 문제가 될 수 있다.

 

재귀 함수의 경우, 함수 호출 스택을 사용하여 함수 호출 순서를 기억하므로, 

함수 호출 비용이 반복문에 비해 크고, 코드가 실행될 때마다 호출 스택을 생성하고 제거하는 '오버헤드'가 발생한다.

이는 재귀 호출의 깊이가 깊어질수록 더 심해짐으로 호출 스택 오버플로우를 방지하기 위해

호출 깊이를 적절히 제한하거나, 재귀 호출 대신 반복문을 사용하여 구현하는 등의 방법을 고려해야 한다.

 

함수 호출 스택

https://4sii.tistory.com/498

함수 호출 스택(call stack)