피보나치 숫자를 적어도 n까지 계산하십시오

Question

사용자가 숫자를 입력 할 수있는 함수를 만들려고합니다. 그 결과는 피보나치 수를 입력까지 포함하고 결과는 입력이 시리즈. 예를 들어 4의 입력은 [0, 1, 1, 2, 3, 5]을 반환하지만 3의 입력은 [0, 1, 1, 2, 3]을 반환합니다. 아래 함수를 사용하여이 작업을 수행했습니다 :

def fibonacci(n): 
     series = [0] 
     if (n == 0): 
      pass 
     else: 
      series.append(1) 
      if (n == 1): 
       pass 
      else: 
       while(series[len(series)-1] < n): 
        newValue = series[len(series)-1] + series[len(series)-2] 
        series.append(newValue) 
     print(series) 

그러나 이제는 재귀 적으로 어떤 아이디어를 사용하고 싶습니까?

Answer 1

가능한 솔루션은 다음

def fibo_up_to(n): 
    if n < 2: 
     return [1,1] 
    else: 
     L = fibo_up_to(n-1) 
     if L[-1] < n: 
      L.append(L[-1] + L[-2]) 
     return L 

아이디어는 그 다음 가능한 한 요소를 추가하면 n-1 미만 사람들의 목록을 요청할 수 있습니다 n 이하의 모든 피보나치 수의 목록을 반환하는 것입니다 . 이것은 처음 두 숫자가 [1, 1] 인 것으로 정의하면 2에서 작동합니다. [0, 1]을 사용하면 다음에 하나의 요소만으로 충분하지 않기 때문에 2에 대한 문제가 발생합니다.

이 코드는 시간에 비효율적이지 않습니다 (fibonacci는 이중 재귀입니다. 이것은 간단한 재귀입니다). 그러나 많은 스택 공간을 사용합니다.