재귀호출 sum 과 분할정복 sum

sums.py

import dis


def recursive_sum(n):
    print('recursive 호출', n)
    if n == 1:
        return 1
    return n + recursive_sum(n-1)


def fast_sum(n):
    print('fast 호출', n)
    if n == 1:
        return 1
    if n % 2 == 1:
        return fast_sum(n-1) + n
    return 2*fast_sum(n//2) + (n//2) ** n


# recursive_sum(20)
# print('\n\n\n')
# fast_sum(20)

dis.dis(recursive_sum)
print('-------------------------------------------------------------')
dis.dis(fast_sum)

#   5           0 LOAD_GLOBAL              0 (print)
#               2 LOAD_CONST               1 ('recursive 호출')
#               4 LOAD_FAST                0 (n)
#               6 CALL_FUNCTION            2
#               8 POP_TOP
#
#   6          10 LOAD_FAST                0 (n)
#              12 LOAD_CONST               2 (1)
#              14 COMPARE_OP               2 (==)
#              16 POP_JUMP_IF_FALSE       22
#
#   7          18 LOAD_CONST               2 (1)
#              20 RETURN_VALUE
#
#   8     >>   22 LOAD_FAST                0 (n)
#              24 LOAD_GLOBAL              1 (recursive_sum)
#              26 LOAD_FAST                0 (n)
#              28 LOAD_CONST               2 (1)
#              30 BINARY_SUBTRACT
#              32 CALL_FUNCTION            1
#              34 BINARY_ADD
#              36 RETURN_VALUE
# -------------------------------------------------------------
#  12           0 LOAD_GLOBAL              0 (print)
#               2 LOAD_CONST               1 ('fast 호출')
#               4 LOAD_FAST                0 (n)
#               6 CALL_FUNCTION            2
#               8 POP_TOP
#
#  13          10 LOAD_FAST                0 (n)
#              12 LOAD_CONST               2 (1)
#              14 COMPARE_OP               2 (==)
#              16 POP_JUMP_IF_FALSE       22
#
#  14          18 LOAD_CONST               2 (1)
#              20 RETURN_VALUE
#
#  15     >>   22 LOAD_FAST                0 (n)
#              24 LOAD_CONST               3 (2)
#              26 BINARY_MODULO
#              28 LOAD_CONST               2 (1)
#              30 COMPARE_OP               2 (==)
#              32 POP_JUMP_IF_FALSE       50
#
#  16          34 LOAD_GLOBAL              1 (fast_sum)
#              36 LOAD_FAST                0 (n)
#              38 LOAD_CONST               2 (1)
#              40 BINARY_SUBTRACT
#              42 CALL_FUNCTION            1
#              44 LOAD_FAST                0 (n)
#              46 BINARY_ADD
#              48 RETURN_VALUE
#
#  17     >>   50 LOAD_CONST               3 (2)
#              52 LOAD_GLOBAL              1 (fast_sum)
#              54 LOAD_FAST                0 (n)
#              56 LOAD_CONST               3 (2)
#              58 BINARY_FLOOR_DIVIDE
#              60 CALL_FUNCTION            1
#              62 BINARY_MULTIPLY
#              64 LOAD_FAST                0 (n)
#              66 LOAD_CONST               3 (2)
#              68 BINARY_FLOOR_DIVIDE
#              70 LOAD_FAST                0 (n)
#              72 BINARY_POWER
#              74 BINARY_ADD
#              76 RETURN_VALUE