피보나치 수 - 재귀함수 사용하여 풀기

앞에서 적었던 피보나치를 재귀 함수를 이용하여 풀어 보았다.

스쿼드 진행 중에 내준 숙제로 기존에 풀었던 방식이 아닌 재귀함수를 사용하여 풀어 보자는 게 숙제였다.

 

def solution(n):
    if n <= 1  : return n
    return solution(n-1) + solution(n-2)

 

해당 코드가 간단한 재귀적으로 피보나치 수를 찾는 방식이다.

그러나 스쿼드 중에 들었던 내용중 중복부분이 많기도 해서 그 부분 때문에 시간 복잡도가 기하급수적으로 증가하게 됨을 알게 되었다.

그래서 한번 계산 했던 부분은 따로 기록해 두었다가 호출시 기록해 둔 내용을 리턴하는 방향으로 코드를 수정해 주었다.

즉 중복으로 사용하는 부분을 없앤 것이다.

 

import sys
sys.setrecursionlimit(10 ** 7)
visitid = {}
def solution(n):
    answer = 0
    def fibonacci(target):
        global visitid
        if target <= 1: 
            return target
        if target in visitid:
            return visitid[target]
        else:
            result = (solution(n-1) + solution(n-2)) % 1234567
            visitid[target] = result 
        return result
    return fibonacci(n)

 

그러나 아직 해결 하지 못한 부분이 sys를 사용하여 푼 부분이다.

sys를 이용하여 재귀 깊이 제한을 늘린 부분에 있다. 이것을 해결 하기만 하면 좀 더 효율적인 코드가 되지 않을까 하는 생각이 든다.

현대 사회의 기술 부분이 늘어 사용해도 문제는 없을 걸로 생각이 되지만 최악의 상황을 항상 생각해야 하는 개발자에게 제한 조건을 늘려서 풀기보다는 제한 상황에서도 풀리는 코드를 작성해야 하는게 아닌가 하는 생각이 있어 이부분은 실력이 좀 더 늘면 한번더 풀어봐야 할 거 같다.