红宝石递归斐波纳契

Question

本周是我第一次做递归。我能解决的一个问题是斐波纳契的序列到第n个数字;它搞了5分钟后并不难。

但是，我很难理解为什么这与当前的返回语句一起工作。

return array if num == 2 

如果我推到数组，这是行不通的，如果我做一个新的变量序列，并推到的是，它返回正确的答案。我很酷，但我的基本情况说，返回数组，而不是序列。我最初将序列推向数组，结果不是fibs序列。当我试着看看如果我推入序列数组会发生什么，我只解决了这个问题。

我只是希望有人能够解释底下发生了什么，堆栈可能是什么以及问题是如何工作的。

我理解递归的程度，直觉上可以通过假设来使它工作，但我觉得有趣，而不是真正了解它背后的所有原因。

def fib_seq(num) 
    return [0] if num == 1 
    return [] if num == 0 

    array = [0, 1] 
    return array if num <= 2 

    seq = fib_seq(num - 1) 
    seq << seq[-2] + seq[-1] 
end 

Answer 1

通过删除临时array变量可以简化代码。这是一种分心。它也仅适用于num == 2; num < 2将由其他基础案例处理。 num < 0是非法的，应该通过错误检查来处理。

我也加入了明确的回报。显式返回使得返回的内容非常明显，这有助于理解递归。在这种情况下，它是seq。 （“明确的回报是邪恶的！”所有的红宝石的人们哭了。艰难的cookies。良好的作风是不是绝对的）。

def fib_seq(num) 
    # Error check 
    if num < 0 then 
     raise ArgumentError, "The number must be a positive integer" 
    end 

    # Terminating base cases 
    return [] if num == 0 
    return [0] if num == 1 
    return [0,1] if num == 2 

    # Recursion 
    seq = fib_seq(num - 1) 

    # The recursive function 
    seq << seq[-2] + seq[-1] 

    return seq 
end 

现在是一个更清楚一点的是return [0,1] if num == 2是三个基地情况之一递归。这些是终止递归的终止条件。但处理并没有结束。结果不是[0,1]，因为在第一次返回之后，堆栈必须展开。

让我们走过fib_seq(4)。

fib_seq(4) calls fib_seq(3) 
fib_seq(3) calls fib_seq(2) 
fib_seq(2) returns `[0,1]` 

我们已经到了基本案例，现在我们需要展开那堆电话。

对fib_seq(3)的呼叫会在停止的地方继续。 seq从fib_seq(2)返回的是[0,1]。它在末尾添加seq[-2] + seq[-1]并返回[0,1,1]。

fib_seq(4)接下来停下来。由fib_seq(3)返回的seq是[0,1,1]。它将seq[-2] + seq[-1]添加到最后并返回[0,1,1,2]。

堆栈被解开，所以我们找回[0,1,1,2]。

正如你所看到的，实际的计算发生了倒退。 f(n) = f(n-1) + f(n-2)和f(2) = [0,1]。它递归到f(2)这个基本情况，然后退回到f(3)使用结果f(2)和f(4)使用结果f(3)等等。

Answer 2

递归函数需要有一个退出条件以防止它们永远运行。您的递归方法的主要部分如下：

seq = fib_seq(num - 1) 
seq << seq[-2] + seq[-1] 

在Ruby，方法的最后一个表达式被认为是该方法的返回值，所以上面的线是等同于：

seq = fib_seq(num - 1) 
seq << seq[-2] + seq[-1] 
return seq 

让我们运行下来，如果该方法仅包含这两条线会发生什么，与NUM = 4：

call fib_seq(4) 
    call fib_seq(3) 
    call fib_seq(2) 
     call fib_seq(1) 
     call fib_seq(0) 
      call fib_seq(-1) 
      ... 

很明显，T他的结果无限循环，因为我们没有退出条件。我们总是在第一行再次拨打fib_seq，因此代码在最后没有机会到达return声明。为了解决这个问题，让我们在这两条线在开始添加：

array = [0, 1] 
return array if num <= 2 

这些可以被简化到只有：

return [0, 1] if num <= 2 

现在，让我们看到，当我们调用该方法NUM发生了什么 = 4：

call fib_seq(4) 
    4 > 2, exit condition not triggered, calling fib_seq(n - 1) 
    call fib_seq(3) 
    3 > 2, exit condition not triggered, calling fib_seq(n - 1) 
    call fib_seq(2) 
    2 == 2, exit condition triggered, returning [0, 1]! 
    fib_seq(2) returned with seq = [0, 1] 
    add 0 + 1 together, push new value to seq 
    seq is now [0, 1, 1] 
    return seq 
fib_seq(3) returned with seq = [0, 1, 1] 
add 1 + 1 together, push new value to seq 
seq is now [0, 1, 1, 2] 
return seq 
FINAL RESULT: [0, 1, 1, 2] 

所以看起来这种方法工作是NUM值> = 2：

def fib_seq(num) 
    return [0, 1] if num <= 2 

    seq = fib_seq(num - 1) 
    seq << seq[-2] + seq[-1] 
end 

有一个错误左：NUM = 0和NUM = 1都返回[0, 1]。让我们来解决这个问题：

def fib_seq(num) 
    return [] if num == 0 
    return [0] if num == 1 
    return [0, 1] if num == 2 

    seq = fib_seq(num - 1) 
    seq << seq[-2] + seq[-1] 
end 

清理了一点：

def fib_seq(num) 
    return [0, 1].first(num) if num <= 2 
    seq = fib_seq(num - 1) 
    seq << seq[-2] + seq[-1] 
end 

Answer 3

我总是觉得它混乱的时候与实用的风格递归混合势在必行风格突变 - 如果你打算做所有的再分配和手动数组寻找，为什么要使用递归作为循环机制？只需使用一个循环。

这并不是说这个程序不能用更多的功能来表达。在这里，我们分开计算Fibonacci数和生成序列的担忧 - 结果是一个非常容易理解的程序

def fib n 
    def aux m, a, b 
    m == 0 ? a : aux(m - 1, b, a + b) 
    end 
    aux n, 0, 1 
end 

def fib_seq n 
    (0..n).map &method(:fib) 
end 

fib_seq 10 
#=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] 

而另一种方式是为专门生成的序列效率更好 - 下面，我定义使用4个状态变量以相对简单的方式生成序列的功能不足的函数。

注意与输入10的区别 - 这是一个更接近你提出的函数，其中0返回[]尽管the 0^th fibonacci number is actually 0

def fib_seq n 
    def aux acc, m, a, b 
    m == 0 ? acc << a : aux(acc << a, m - 1, b, a + b) 
    end 
    case n 
    when 0; [] 
    when 1; [0] 
    when 2; [0,1] 
    else; aux [0,1], n - 3, 1, 2 
    end 
end 

fib_seq 10 
# => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]