[혼공파] 함수의 활용

that's true

 

재귀함수

팩토리얼 같은것을 구할때, 반복문을 통해 구하는 방법이 있고, 재귀함수로 구하는 방법이 있음

 

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

# 함수 선언 
def factorial(n):
    output =1
    #반복문 돌리기
    for i in range(1, n+1):
        output *= i
    return output

print("1!:", factorial(1))
print("10!:", factorial(10))
print("50!:", factorial(50))
print("100!:", factorial(100))

사실 팩토리얼 50,100 하는거 그냥 100! 이렇게 하고 끝냈는데,, 

학교에서는 팩토리얼 구할때 참 공식에 손으로 열심히 풀었는데,,, 허탈할정도로 빠르다.. ㅋㅋ

 

 

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

재귀 (Recursion): 자기 자신을 호출하는 것을 의미

#함수 선언
def factorial(n):
    #n이 0라고 한다면 1을 리턴
    if n == 0:
        return 1 
    #n이 0이 아니라면 n*(n-1)!을 리턴
    else:
        return n*factorial(n-1)
        
print("1!:", factorial(1))
print("10!:", factorial(10))
print("50!:", factorial(50))
print("100!:", factorial(100))

결과는 위와 동일하다. 

어떤걸 써도 상관은 없다고 하는데, 개인적으로는 재귀함수를 써서 하는게 더 깔끔하고 이해하기가 편하다.

 

재귀 함수의 문제

편하다고 한지 1초 지나서 문제가 나왔다.

같은 것을 기하급수적으로 많이 반복하기 때문에 문제라고 하는데, 메모화를 통해 해결 가능하다.

 

예제가.. 피보나치다. 

(나름 순수 수학과로써 피보나치 리서치 페이퍼와 발표로 A+받았다..ㅎ힣...)

과거 발표자료에서 사용한 이미지1

위의 스토리가 가장 잘 설명을 하고있고 토끼 예제가 가장 간결하다

과거 발표자료에서 사용한 이미지2

다른 수식보다 위의 수식이 피보나치를 이해하는데 가장 빠름, 음수도 가능하다는 점을 알아두자. 

 

너무 잡소리가 많았고... 다시 재귀함수로 피보나치 수열을 구해보자.

 

 

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

#함수를 선언한다
def fibonacci(n):
    if n==1:
        return 1
    if 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(35):", fibonacci(35))

편하게 피보나치 수를 구할 수 있었다.

하지만 수가 커질수록 결과값을 내놓는 시간이 오래 걸렸는데, 35가 4초 걸렸다는 책을 보고 뭣 모르고 100 하려다가 취소했다..

코드를 사용해서 이유를 찾을 수 있다. 

#변수 선언 
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("---")
print("fibonacci(10)계산에 활용된 덧셈 횟수는 {}번입니다.".format(counter))

왜 이렇게 fibonacci(10)을 구하는데 109번을 하는지 알아보자.

(중간에  global 함수 코드는 뒤에서 설명)

혼공파 234p

일단 이런 형태를 tree 형태라고 부르고, 각 지점을 node, 마지막 지점을 leaf라고 한다.

함수 f(10)을 연산하기 위해서 각 노드 값을 계산하려면 덧셈을 한번씩 다해야한다는 것이고, 

한번 구한 값도 처음부터 다시 계산을 해서 느리다는 것이다. 

-> 즉 구조가 효과적이지 않고, 과부하를 가지고 올 수 있는 코드 형태라는 것.

 

 

파이썬은 함수 내부에서 외부에 있는 변수를 참조 못한다고한다. 

참조는 즉 변수에 접근하는것을 이야기하는데, 그걸 해주는게 global 키워드이다.

 

Error에서 Redefining name 'counter' from outer scope 또는 Undefined Variable 'counter'라고 하면 외부에서의 변수 문제인것...

(어렵네이거)

 

 

메모화 

그럼 암튼 저 위에서 계속 반복되는 애들을 해결 어떻게 해주냐. 

메모를 통해서 해결이 가능하다. 

딕셔너리를 사용해서 한번 계산한 값을 저장 (메모)해주고, 그 값을 돌려주면서 좀 빠르게 하는 것이다. 

 

메모화를 한 위의 피보나치수를 다시 구해보자.

#메모 변수를 만든다
dictionary = {
    1: 1,
    2: 1
}


#함수를 선언 
def fibonacci(n):
    if n in dictionary:
        #메모가 되어있으면 메모된 값 출력
        return dictionary[n]
    else:
        #메모가 안된거면 값을 구한다 
        output = fibonacci(n-1) + fibonacci(n-2)
        dictionary[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))

위에서 바뀐건 처음에 dictionary하나인데 속도가 훨씬 빨라졌다, 그냥 누르면 나오는 정도. 

 

 

조기 리턴

리턴을 미리 해주냐, 나주에 해주냐 그 차이인데, 코드를 한번 봐보쟈.

#####if else 구문에서 각 마지막 구간에 return #####
def fibonacci(n):
    if n in dictionary:
        #메모가 되어있으면 메모된 값 출력
        return dictionary[n]
    else:
        #메모가 안된거면 값을 구한다 
        output = fibonacci(n-1) + fibonacci(n-2)
        dictionary[n] = output
        return output


#####조기리턴  #####
def fibonacci(n):
    if n in dictionary:
        #메모가 되어있으면 메모된 값 리턴
        return dictionary[n]
    output = fibonacci(n-1) + fibonacci(n-2)
    dictionary[n] = output
    return output

두개의 차이는... else대신에 들여쓰기가 되지 않았다는건데, 

솔찍히 아직 저 두 코드에 큰 차이는 잘 모르겠다. 

 

 

 

물어볼게 많은 단원이다..

다시 한번 함수쪽은 천천히 복습하고 넘어가야겠드아.,,