ruby - 使用两个递归理解递归概念

Question

我正在尝试解决合并排序问题，但我迷失在递归概念中。所以为了让自己更好地理解，我举了一个小例子。

对于下面的程序，n= 2 我得到的答案是 0,1,2，我完全理解使用堆栈和一个一个地返回堆栈值的概念通过 puts n 完成递归后。

 def one(n)
  if n < 0
   return
  end
  one(n-1)
  puts n
 end

但是当我尝试使用如下所示的另一个递归时，我完全迷失了答案 0,0,1,0,0,1,2 的原因和方式。谁能简单解释一下？

 def one(n)
  if n < 0
   return
  end
  one(n-1)
  one(n-1)
  puts n
 end

请添加足够的说明，说明这两种递归如何协同工作。

Answer 1

这是第二次递归的图形表示。行表示操作的顺序；递归级别的列:

n = 2
return if n < 0
one(1) ->        n=1
                 return if n < 0
                 one(0) ->        n=0
                                  return if n < 0
                                  one(-1) ->       n=-1
                                                   return if n < 0
                                                   <-

                                  one(-1) ->       n=-1
                                                   return if n < 0
                                                   <-
                                  puts 0
                                  <-

                 one(0) ->        n=0
                                  return if n < 0
                                  one(-1) ->       n=-1
                                                   return if n < 0
                                                   <-

                                  one(-1) ->       n=-1
                                                   return if n < 0
                                                   <-
                                  puts 0
                                  <-
                 puts 1
                 <-

  one(1) ->      n=1
                 << same as above, resulting in `puts 0`, `puts 0`, `puts 1` >>
                 <-
  puts 2

将每个递归级别(列)视为一个单独的方法。它执行一些操作然后调用另一个方法。在这种情况下，它会调用自己，但您不应该那样想；只需将其视为调用某种方法即可。最终该方法返回，可能带有一个值(但这里没有)，并且该方法以正常方式继续到下一条语句(行)。最终它返回到调用它的方法。这恰好是相同的方法，但再次将其视为某种方法。

相比之下，这就是您的第一次递归所发生的情况:

n = 2
return if n < 0
one(1) ->        n=1
                 return if n < 0
                 one(0) ->        n=0
                                  return if n < 0
                                  one(-1) ->       n=-1
                                                   return if n < 0
                                                   <-
                                  puts 0
                                  <-
                 puts 1
                 <-
puts 2