[BinarySearch] 나무 자르기 (iterative vs recursion)

여기서 에러가 났던 부분은 시간제한을 맞추지 못했던.

 

Recursion으로 BinarySearch를 수행하면 실패하지만

 

while문으로 해결하면 통과가 가능하다.

 

Recursion

import time
start_time = time.time()

n, target = map(int, input().split())
trees = list(map(int, input().split()))
trees.sort()
def BinarySearch(array, target, start, end):
    if start > end:
        return None
    
    mid = (start+end)//2
    lefty = 0
    for tree in trees:
        if tree > mid:
            lefty += tree - mid
    if lefty == target:
        return mid
    elif lefty > target:
        return BinarySearch(array, target, mid+1, end)
    else:
        return BinarySearch(array, target, start, mid-1)

res = BinarySearch(trees, target, 0, max(trees))
print(res)

While

n, m = map(int, input().split())
trees = list(map(int, input().split()))
trees.sort()
# Using start, mid, end
start = 0
end = max(trees)

# Binary Search
H = 0
while(start <= end):
    total = 0
    mid = (start+end)//2
    for tree in trees:
        if tree > mid:
            total += tree - mid
    if total < m: # object is to get maximum m, thus if total is smaller than, move end position to left.
        end = mid-1
    else: # if total is larger than m
        start = mid+1
        H = mid # 

print(H)

recursion vs while loop

softwareengineering.stackexchange.com/questions/182314/recursion-or-while-loops

Recursion or while loops

Recursion is not intrinsically better or worse than loops - each has advantages and disadvantages, and those even depend on the programming language (and implementation).

Technically, iterative loops fit typical computer systems better at the hardware level: at the machine code level, a loop is just a test and a conditional jump, whereas recursion (implemented naively) involves pushing a stack frame, jumping, returning, and popping back from the stack. OTOH, many cases of recursion (especially those that are trivially equivalent to iterative loops) can be written so that the stack push / pop can be avoided; this is possible when the recursive function call is the last thing that happens in the function body before returning, and it's commonly known as a tail call optimization (or tail recursion optimization). A properly tail-call-optimized recursive function is mostly equivalent to an iterative loop at the machine code level.

--- 정리하자면 ---

recursion과 while은 서로 장단점이 있기 때문에 특정한 것이 우월하다고 말할 수 없다.

loop(while과 같은)은 hardware level에서 장점이 있고

recursion은 machine code level에서 장점이 있다.

    What is machine code?

    Machine language, or machine code, is a low-level language comprised of binary digits (ones and zeros).

그런데 마지막 부분에서 tail call optimization을 하면 좀더 효율적인 recursion수행이 가능하다고 한다.

 

    What is tail call optimization?

   Recursion은 함수를 call 할때마다 stack이 쌓이게 되는데, 만약 return전에 계속 call이 되어버리면 stack이 계속 깊게 쌓임. Recursion의 단점은 call이 너무 많아지면 stack이 깊어지는 것이다.

'다시 말해서 N의 값이 충분히 크다면 마음 놓고 재귀 호출을 사용할 수 없다는 뜻이다. 해결책은 크게 두 가지다.'

1. Iterative solution
2. Tail recursion elimination

philosophical.one/posts/tail-recursion-in-python/

Tail Recursion in Python