[Python] 재귀함수 : 피보나치 수, 팩토리얼

백준 피보나치 문제를 해결하던 중 답은 맞게 나오는데 도저히 넘어가질 않아서

 

원인을 찾던 중 재귀함수의 형태로 코딩을 해야한다는 것을 알았다. (for문이 좋은데..)

 

재귀함수란??

 

자기 자신을 재참조 하는 함수로 정의 단계에서 자기 자신을 사용하는 함수를 의미합니다.

 

팩토리얼을 예시로 설명하면 for문을 사용했을 때 코드는 다음과 같습니다.

def factorial():
    answer = 1
    N = int(input())
    for i in range(1,N+1):
        answer *= i

    return print(answer)


factorial()

for문으로 정의했을 때에는 정수 n을 받아 1부터 곱하는 형태로 정의하였다면

 

재귀함수는

def fact(n:int) -> int:
    if n == 0:
        return 1
    elif n == 1:
        return 1
    else:
        return n*fact(n-1)
    
if __name__ == '__main__':
    n = int(input())
    print(fact(n))

정의한 함수의 이름이 함수 내용에 등장하는 형태입니다.

 

 

이 경우 좀 더 간편한 코딩을 할 수 있지만 연산이 길어질 경우 처리속도가 기하급수적으로 증가하기 떄문에

처리속도를 고려한 코드 작성을 해야합니다.

 

피보나치 수도 재귀함수로 작성하면 다음과 같습니다.

def fib(n: int) -> int:
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

                
if __name__ == '__main__':
    n = int(input())
    print(fib(n))

풀이한 백준 알고리즘 문제의 경우 범위가 좁기 때문에 작성한 코드로 정답이 됐지만

더 넓은 범위의 데이터에서 작동할 경우 매우 오래걸리게 되는 코드입니다.

 

print 함수의 경우도 시간이 오래걸리는 것으로 알고 있지만 근본적으로 함수 내의 구조를 수정할 필요가 있어보입니다.