함수의 활용(1) 재귀 함수 / 재귀 함수의 문제 / global 키워드

함수를 만드는 기본적 방법을 알고 있어도, 실제로 함수들이 어떻게 사용되는지 많이 접하지 않으면 함수를 제대로 활용할 수 없음. 함수가 어떤 식으로 활용되는지 살펴봐야 함.

---

재귀 함수

* 재귀 recursion : 자기 자신을 호출하는 것

* 재귀 함수 : 함수를 정의하는 내부 안에 자기 자신(즉 만들고 있는 함수)을 호출하는 것

 

* 팩토리얼 factorial  

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

 

* 팩토리얼을 구하는 방법

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

def factorial(n):
    output = 1
    for i in range(1, n + 1):
        output *= i
    return output

print(factorial(5))

</>
120

 

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

팩토리얼을 재귀표현으로 다시 나타내기

factorial(n) = n * factorial(n - 1) (n >= 1 일 때) factorial(0) = 1

 

재귀 표현을 이용해 factorial(4) 구하기

f(4) = 4 * f(3) = 4 * 3 * f(2) = 4 * 3 * 2* f(1) * f(0) = 4 * 3 * 2 * 1 * 1

 

코드로 나타내기 : 재귀 함수이므로 함수를 정의하는 내부에서 같은 함수를 호출함

def factorial(n):
    # n이 0이라면 리턴
    if n == 0 :
        return 1
    # n이 0이 아니라면 n * (n-1)!을 리턴
    else:
        return n * factorial(n-1)

print(factorial(5))

</>
120

---

* 피보나치 수열 : '토끼는 어떠한 속도로 번식하는가'와 같은 연구에 사용되는 수열. 재귀함수의 한 종류

[피보나치 수열의 규칙] 처음에는 토끼가 한 쌍만 존재합니다. 두 달 이상 된 토끼는 번식할 수 있습니다. 번식한 토끼는 매달 새끼를 한 쌍씩 낳습니다. 토끼는 죽지 않는다고 가정합니다.

 

피보나치 수열 그림으로 나타냄

 

---

재귀 함수의 문제

재귀 함수는 상황에 따라 같은 것을 기하급수적으로 많이 반복하는 문제가 있음 ➡️ 계산 속도가 너무 오래 걸리게 됨

코드로 이를 알아보면 같은 것을 여러 번 연산하기 때문에 시간이 오래 걸리게 되는 것.

1) 재귀 함수로 구현한 피보나치 수열(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))

</>
fibonacci(1): 1
fibonacci(2): 1
fibonacci(3): 2
fibonacci(4): 3
fibonacci(5): 5

 

2) 재귀 함수로 구현한 피보나치 수열(2)

# 변수 선언                                                               
counter = 0                                                           
                                                                      
# 함수 선언                                                               
def fibonacci(n):                                                     
    print("fibonacci({})를 구합니다.".format(n))                           
    global counter                                                    
    counter += 1                                                      
    # 피보나치 수열 구하기                                                     
    if n == 1:                                                        
        return 1                                                      
    if n ==2:                                                         
        return 1                                                      
    else:                                                             
        return fibonacci(n-1) + fibonacci(n-2)                        
                                                                      
# 함수 호출                                                               
fibonacci(10)                                                         
print("fibonacci(10) 계산에 활용된 덧셈 횟수는 {}번 입니다.".format(counter))        

</>
... 생략 ...
fibonacci(1)를 구합니다.
fibonacci(2)를 구합니다.
fibonacci(10) 계산에 활용된 덧셈 횟수는 109번 입니다.

피보나치 수열 10번째를 구하는데 109번이나 연산함. 

---

[덧셈 횟수가 기하급수적으로 늘어나는 이유]

트리 : 위와 같은 형태의 그림

노드 : 트리에 있는 각각의 지점

리프 : 노드 중 가장 마지막 단계의 노드

트리 내부에 있는 각각의 노드 값을 계산하려면 덧셈을 한 번씩 해야하지만, 노드가 한 번에 두 개씩 달려있음. 현재 코드의 재귀 함수ㅡㄴ 한 번 구했떤 값이라도 처음부터 다시 계산해야 하기 때문에 계산 횟수가 기하급수적으로 늘어나게 되는 것

 

---

global 키워드

파이썬은 함수 내부에서 함수 외부에 있는 변수를 참조하지 못함.

변수에 접근하는 것을 참조라고 부름.

함수 내부에서 함수 외부에 있는 변수라는 것을 설명하기 위해 global 키워드를 사용

global 변수 이름

global 키워드의 존재를 생각하지 않고 작성하다보면

W0621 : Redefining name 'counter' from outer scope 또는

E0602 : Undefined variable 'counter' 가 나타나게 됨