python中的斐波那契，递归到列表中 [英] Fibonacci in python, recursively into a list

问题描述

我正在练习一些代码，我想做的一件事是将斐波那契数列递归地放入一个列表中.我已经设法在没有递归的情况下做到了，但这并不太难.感谢任何可以提供任何帮助的人.

I am practicing with some code, and one thing I am trying to do is have the Fibonacci sequence placed recursively into a list. I have managed to do it without recursion, but that is not too difficult. Thank you to anyone who can offer any help.

#python 2

arr = [1, 1]
n=15
def Fib(n):
  tmp = arr[-1] + arr[-2]
  if n == 0:
    return 0 #base case 1
  elif n == 1:
    return 1  #base case 2
  else:
    return Fib(n-1) + Fib(n-2) #recursive call
  arr.append(tmp)
  return arr
Fib(n)
print arr

推荐答案

试运行您的代码.你会发现

Do a dry run of your code. You will find that

arr.append(tmp)
  return arr

上面的代码永远不会被执行，因为它在 if-else 条件之一中返回了之前的答案.

The above code never gets executed as it returns the answer before in one of the if-else conditions.

以下代码有帮助:

arr = []
n=15
def Fib(n):

  if arr[n] != -1:
    return arr[n]
  if n == 0:
    arr[0] = 0
    return 0 #base case 1
  elif n == 1:
    arr[1] = 1;
    return 1  #base case 2
  else:
    arr[n] = Fib(n-1) + Fib(n-2);
    return arr[n];

for i in range(n+1):
    arr.append(-1);
Fib(n)
print arr

我正在做的是，最初我将 -1 分配给列表中的所有索引，表明从未访问过此特定状态.有一次，我访问了一个特定的状态，我将它的解决方案存储在该索引的 arr 中.如果解决方案状态已被访问并再次遇到，我会立即返回该索引处可能的解决方案，而不会进一步递归.

What I am doing is that initially I am assigning -1 to all the indexes in the list telling that this particular state has never been visited. Once, I visit a particular state, I store its solution in the arr at that index. And if the solution state has been visited and is encountered again, I straight away return the solution possible at that index without recursing further on it.

这篇关于python中的斐波那契，递归到列表中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！