[자료구조] 재귀함수 파이썬 (recursive, iterative, decorator, reduce)

Fibonacci

피보나치 (recursively & iteratively)

삼항 연산자(Ternary operators)로 풀이 (출처는 아래에)

# basic recusrive solution
def fibo(n):
    return fibo(n-1) + fibo(n-2) if n >= 2 else n

# basic iterative solution
def fibo(n):
    if n < 2:
        return n

    a, b = 0, 1
    for i in range(n-1):
        a, b = b, a + b

    return b

# iterative w/ DP
def fibo(n):
    if n < 2:
        return n
    cache = [0 for _ in range(n+1)]
    cache[1] = 1
    
    for i in range(2, 100+1):
        cache[i] = cache[i-1] + cache[i-2]

    return cache[n]

# recursive w/ DP
def fibo(n):
    cache = [-1 for _ in range(n+1)]

    def iterate(n):
    	# 기저사례 1.
    	if i < 2:
	    return i

	# 기저사례 2.
        if cache[n] != -1:
	    return cache[n]

	# 기저사례 충족 못할 시 값을 실제로 구함
	cache[n] = iterate(n-1) + iterate(n-2)
	return cache[n]

    return iterate(n)

Factorial

팩토리얼 (iteratively & recursively & reduce & DP)

## iteratively
def factorial_iter(n):
    ret = 1
    for i in range(1, n+1):
        ret *= i
    return ret

## recursively
def factorial_recu(n):
    return n * factorial_recu(n-1) if n > 1 else 1

## reduce
from functools import reduce

def factorial_reduce(n):
    return reduce(lambda x, y: x * y, range(1, n+1))

## DP w/o Decorator
cache = {}

def factorial_recursive(n):
    global cache

    if n in cache:
        return cache[n]
    elif n <= 1:
        return 1
    else:
        cache[n] = n * factorial_recursive(n-1)
	return cache[n]

    return n * factorial_recursive(n-1) if n > 1 else 1

## DP w/ Decorator
def in_cache(func):
    cache = {}
    def wrapper(n):
        if n in cache:
            return cache[n]
        else:
            cache[n] = func(n)
            return cache[n]
    return wrapper

@in_cache
def factorial_recursive(n):
    return n * factorial_recursive(n-1) if n > 1 else 1

DP를 활용하는데 decorator가 등장한다.

출처: shoark7.github.io/programming/algorithm/several-ways-to-solve-factorial-in-python#3c

---

Decorator?

함수를 받아 명령을 추가한 뒤 이를 다시 함수의 형태로 반환하는 함수이다.
함수의 내부를 수정하지 않고 기능에 변화를 주고 싶을 때 사용한다 .
일반적으로 함수의 전처리나 후처리에 대한 필요가 있을때 사용을 한다.
또한 데코레이터를 이용해, 반복을 줄이고 메소드나 함수의 책임을 확장한다

출처: medium.com/@hckcksrl/python-%EB%8D%B0%EC%BD%94%EB%A0%88%EC%9D%B4%ED%84%B0-decorator-980fe8ca5276

---

좀 더 많은 예시가 있는 자료

nested function으로 사용하는 것보다는 class로 만들어서 사용하는 것이 훨씬 깔끔하고 가독성도 좋다.

import datetime


class DatetimeDecorator:

        def __init__(self, f):

                self.func = f


        def __call__(self, *args, **kwargs):

                print datetime.datetime.now()

                self.func(*args, **kwargs)

                print datetime.datetime.now()


class MainClass:

        @DatetimeDecorator

        def main_function_1():

                print "MAIN FUNCTION 1 START"


        @DatetimeDecorator

        def main_function_2():

                print "MAIN FUNCTION 2 START"


        @DatetimeDecorator

        def main_function_3():

                print "MAIN FUNCTION 3 START"



my = MainClass()

my.main_function_1()

my.main_function_2()

my.main_function_3()


# 출처: https://bluese05.tistory.com/30 [ㅍㅍㅋㄷ]

출처: bluese05.tistory.com/30

---

reduce 함수는 전에 활용한 적이 있다. link

 

from functools import reduce (docs: link)

Apply function of two arguments cumulatively to the items of iterable, from left to right, so as to reduce the iterable to a single value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5).