[파이썬] recursion(재귀)와 메모화의 중요성

함수의 활용

재귀함수

재귀(recursion)은 **‘자기 자신을 호출하는 것’**을 의미함

재귀함수로 factorial 연산을 하는 예제

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

재귀함수의 문제

재귀함수의 경우 한번 구했던 값을 계속 구해야하기 때문에 계산이 기하급수적으로 늘어나는 특성을 지니고 있다

e.g. factorial(5)

 5*factorial(4) → 5*4*factorial(3) → factorial(3)을 한번 계산함

      4*factorial(3) → 근데 여기서 또해야됨

     …..1*factorial(0) → 결론적으로 factorial(0)은 매 계산마다 다시 계산되야함

메모화

같은 값이 여러번 계산되는게 문제라면 한 번 계산한 값은 다시 계산할 필요가 없도록 메모해두면 된다

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

print(fibonacci(10),counter)

counter=0
dict={1:1,2:1}
def fibonacci_memo(n):
    global counter
    counter+=1
    if n in dict:
        return dict[n]
    else:
        dict[n] = fibonacci_memo(n-1) + fibonacci_memo(n-2)
        return dict[n]

print(fibonacci_memo(10),counter)

#result
55 109
55 17

조기 리턴

return 키워드를 중간에 사용하는 것으로 함수가 더 이상 작동할 필요가 없을 때 빠르게 종료시키기 위해 사용함

리스트 평탄화 예제

li = [[1,2,3],[4,[5,6]],7,[8,9]]

def flat(data):
    output=[]
    for i in data:
        if type(i) == list:
            output += flat(i)
        else:
            output.append(i)
    return output
    print(output)

flat(li)

#result
[1,2,3,4,5,6,7,8,9]

파이썬 튜터를 적극 활용할 것