13. 파이썬 - 함수의 활용

지난 시간까진 함수를 어떻게 만들고, 사용하는지에 대해 알아보았다.

이번엔 이 함수들을 적재적소에 활용하는 방법에 대해 알아보겠다.

 

재귀 함수

우리는 어릴때 팩토리얼 이라는 연산자를 배웠다. (근데 난 수학을 잘 못해서 솔직히 말하면 까먹고 있었다.)

나처럼 까먹고 있을 사람들을 위해서.

n! = n * (n - 1) * (n - 2) * . . . 1

이러한 팩토리얼을 구하는 방법은 두가지로 구분할 수 있다.

• 반복문으로 팩토리얼 구하기
• 재귀 함수로 팩토리얼 구하기

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

먼저 반복문을 이용하여 팩토리얼을 구하는 방법을 소개하겠다.

def factorial(n) :
    output = 1 # 어떤 값이라도 1을 곱하면 변화가 없기 때문에 1로 설정한 것이다.
    for i in range(1,n+1) :
        output *= i
    return output

print("1!: ", factorial(1))
print("2!: ", factorial(2))
print("3!: ", factorial(3))
print("4!: ", factorial(4))
print("5!: ", factorial(5))

1부터 n까지 곱하기만 하면 된다.

따라서 팩토리얼 함수를 저렇게 만들면 가능하다.

output의 설정을 1로 해놓은 이유는 어떤 값이라도 1을 곱하면 변화가 없기 때문에 1로 설정해놓은 것이다.

 

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

두번째 방법은 재귀 함수를 이용하는 것이다. 여기서 나오는 재귀란, '자기 자신을 호출하는 것'을 의미한다.

# 재귀 함수를 사용해 팩토리얼 구하기
def factorial(n) :
    if n == 0 :
        return 1
    else :
        return n * factorial(n-1)
    
print("1!: ", factorial(1))
print("2!: ", factorial(2))
print("3!: ", factorial(3))
print("4!: ", factorial(4))
print("5!: ", factorial(5))

n이 0일 경우에는 1을 리턴하도록 설정해놓고, 나머지는 자기 자신을 하나씩 빼면서 돌며 n과 곱하는 방법이다.

 

하지만 유용한 재귀함수에도 문제는 존재하기 마련이다.

 

재귀 함수의 문제

재귀 함수는 상황에 따라서 같은 것을 기하급수적으로 많이 반복한다는 문제가 있다.

이 때문에 숫자가 늘어남에 따라 연산하는 작업량이 엄청나게 많아지다 보니, 컴퓨터의 연산 적으로나 , 코드의 질적으로나 문제가 되는것이 있다.

 

이 문제를 가장 단적으로 보여주는 재귀 함수를 하나 더 알아보겠다.

# 재귀 함수로 구현한 피보나치 수열(1)
def fibonacci(n) :
    if n == 1 :
        return 1
    elif n == 2 :
        return 1
    else :
        return fibonacci(n-1) + fibonacci(n-2)
    
print("fibonacci(1): ", fibonacci(1))
print("fibonacci(2): ", fibonacci(2))
print("fibonacci(3): ", fibonacci(3))
print("fibonacci(4): ", fibonacci(4))
print("fibonacci(5): ", fibonacci(5))

위 코드는 피보나치 수열이라고 불리우는 재귀함수를 구현해놓은 코드이다.

피보나치 수열의 규칙은 다음과 같다.

• 1번째 수열 = 1
• 2번째 수열 = 1
• n번째 수열 = (n-1)번째 수열 + (n-2)번째 수열

위의 코드를 이러한 규칙으로 풀어나가면, 5가 마지막 숫자이기에 딱히 큰 숫자와, 큰 시간이 걸리지 않는다.

하지만, 입력 수를 35,40 정도로 넣어보면 엄청나게 많은 숫자가 프린트 될 뿐만아니라, 연산시간이 엄청나게 오래 걸린다.

 

왜 이럴까?

# 재귀 함수로 구현한 피보나치 수열(2)
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): ", fibonacci(10))
print("fibonacci(10)계산에 활용된 덧셈 횟수는 {}번입니다".format(counter))

그 궁금증을 해결하기 위해 피보나치 수열 함수에 카운터를 넣어보았다. 

 

여기서 알아갈 포인트는, 피보나치 수열 함수 외부에 counter라는 변수를 선언했다.

그리고 함수 내부에서 사용을 진행했다. 파이썬은 애초에 외부에 있는 변수는 참조가 안된다.

하지만 global이라는 키워드를 사용하여 밖에 있는 counter이라는 변수를 사용한다. 라는 뜻으로 인식하게 도움을 주었다.

 

얼마나 어떻게 돌아가길래 그리 시간이 걸리는지.

위 코드의 실행결과이다.

피보나치 수열로 10의 연산을 해보았다. 결과는 55. 활용된 횟수는 무려 109번이나 된다.

따라서 55의 수를 찾기 위해 109번이나 함수를 돌렸다는 의미이다. 10이 이정도인데 35,40은 상상을 초월하게 된다.

왜 이렇게 진행이 되는지 설명해보겠다.

왼쪽의 그림은 트리라는 형태의 그래프이다.

트리에 있는 각각의 지점을 노드라고 하고, 노드 중에 가장 마지막에 있는 노드를 리프 노드라고 한다.

 

트리 내부에 있는 각각의 노드 값을 계산하려면 덧셈을 한 번씩 해야한다. 그런데 노드가 한번에 두개 달려 있다.

한번 구한 값은 그것으로 계산이 끝나면 좋겠지만, 현재 코드의 재귀 함수는 한 번 구했던 값이라도 처음부터 다시 계산을 해야한다. 그래서 계산횟수가 기하급수적으로 오른 것이다. 

 

 

 

이러한 문제를 해결할 수 있는 방법이 존재한다.

 

메모화

현재 문제는 같은 값을 구하는 연산을 반복하고 있기 때문에 발생하는 것이다.

따라서 같은 값을 한 번만 계산하도록 코드를 수정하면 된다.

# 메모화

# 메모 변수를 만듭니다.
dic = {
    1: 1,
    2: 1
}

def fibonacci(n) :
    if n in dic :
        # 메모가 되어있으면 메모된 값을 리턴
        return dic[n]
    else :
        output = fibonacci(n - 1) + fibonacci(n - 2)
        dic[n] = output
        return output
    
print("fibonacci(10): ", fibonacci(10))
print("fibonacci(20): ", fibonacci(20))
print("fibonacci(30): ", fibonacci(30))
print("fibonacci(40): ", fibonacci(40))
print("fibonacci(50): ", fibonacci(50))

딕셔너리를 이용하여 한번 계산한 값을 저장할 수 있다. 

 

1과 2는 피보나치 수열에서 모두 1로 계산이 되니 기본으로 딕셔너리에 추가해 주었고, 이외에 모든 수들은 재귀함수의 피보나치 수열을 이용하여 딕셔너리에 넣어준다.

 

이를 메모한다고 표현한다.

딕셔너리에 값이 메모되어 있으면 수행하지 않고 곧바로 메모된 값을 돌려주면서 코드의 속도를 빠르게 만드는 것이다.

 

이전에는 40,50을 돌려도 엄청 시간이 걸렸지만, 메모화를 하면 시간이 엄청 단축된다.

 

조기 리턴

과거에는 프로그래밍을 할 때 변수는 반드시 앞 쪽에 몰아서 선언해야하고, 리턴은 반드시 뒤쪽에서 해야 한다는 비공식적인 규칙이 있었다. 하지만 요즘엔 값을 리턴하고 싶은 구문에 그냥 바로 리턴을 시키는 것이 맞다라는 인식이 널리 퍼지게 되었다.

# 메모화

# 메모 변수를 만듭니다.
dic = {
    1: 1,
    2: 1
}

def fibonacci(n) :
    if n in dic :
        # 메모가 되어있으면 메모된 값을 리턴
        return dic[n]
        
    output = fibonacci(n - 1) + fibonacci(n - 2)
    dic[n] = output
    return output
    
print("fibonacci(10): ", fibonacci(10))
print("fibonacci(20): ", fibonacci(20))
print("fibonacci(30): ", fibonacci(30))
print("fibonacci(40): ", fibonacci(40))
print("fibonacci(50): ", fibonacci(50))

따라서 앞서 살펴본 메모화된 피보나치 수열에서도 else를 선언해 꼭 다른 리턴을 보여주기보다, 그냥 메모가 되어있으면

값을 리턴하는 if 문 하나만 생성해놓고 나머지는 기존의 코드로 돌리게 설정해놓아도 크게 상관이 없다라는 것이다.

 

정리
재귀 함수는 내부에서 자기 자신을 호출하는 함수를 의미한다.
메모화는 한 번 계산한 값을 저장해 놓은 후, 이후에 다시 계산하지 않고 저장된 값을 활용하는 테크닉이다.
조기 리턴은 함수의 흐름 중간에 return 키워드를 사용해서 코드 들여쓰기를 줄이는 등의 효과를 가져오는 테크닉이다.