팩토리얼(factorial)

$n! = n\times(n-1)\times(n-2)\times...\times1$

반복문으로 팩토리얼 구하기

# 팩토리얼 with 반복문

def factorial(n) :
    output =  1 # 초기값
    for i in range(1, n+1) : # 1, 2, ..., n
        output *= i # output = output * i
    return output

# 팩토리얼 함수 호출
print(factorial(5))
print(factorial(10))
print(factorial(15))

재귀 함수로 팩토리얼 구하기

# 팩토리얼 함수 with 재귀함수(recursion)

def factorial(n) :
    if n == 1 :
        return 1
    else :
        return n * factorial(n-1)

# 팩토리얼 함수를 호출
print(factorial(5))

factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
# 따라서
factorial(5) = 5 * 4 * 3 * 2 * 1

피보나치 수열

# 피보나시 수열

def fibonacci(n) :
    if n == 1 :
        return 1
    if n == 2 :
        return 1
    else :
        return fibonacci(n-1) + fibonacci(n-2)

# 피보나치 함수 호출
print(fibonacci(3))
print(fibonacci(10))

1 | 1 | (1+1) | (1+1)+1 | (1+1)+(1+1+1) |

피보나치 수열 호출 횟수

# 피보나시 수열
counter = 0 # 전역함수

def fibonacci(n) :
    global counter
    counter += 1
    if n == 1 :
        return 1
    if n == 2 :
        return 1
    else :
        return fibonacci(n-1) + fibonacci(n-2)

# 피보나치 함수 호출
print(fibonacci(30))
print("총 함수 호출 횟수 :", counter)

메모화

# 피보나시 수열 with 메모화

diction = {
    1: 1,
    2: 1
}

def fibonacci(n) :
    if n in diction : # n이 딕셔너리에 있으면
        return diction[n]
    else : # n이 딕셔너리에 없으면
        output = fibonacci(n-1) + fibonacci(n-2)
        diction[n] = output # 키 diction[n] = 요소 output
        return output

print(fibonacci(50))