Recursion

base part : recursive x

recursive part : recursive call

 

무작정 재귀를 사용하면 스택에 쌓이니까 무조건 쓰면 안된다

 

drawback of recursion

memoization : 재귀로 인해서 스택 오버플로우를 방지하기 위해서 반복 되는계산을 피해준다

def fib(n):
    if n in fib_memo:
        return fib_memo[n]
    result = n if n <= 1 else fib(n-1) + fib(n-2)
    fib_memo[n] = result
    return result