什么是递归？它是如何工作的？

Question

有人可以解释究竟什么是递归(以及它如何在Ruby中工作,如果这不是太多要求).我遇到了一个依赖递归的冗长代码片段,它使我感到困惑(我现在丢失它,并不完全相关).

Answer 1

递归函数/方法调用自身.对于递归算法终止你需要一个基本情况(例如在功能没有条件不递归调用本身),你还需要确保你在每次递归调用更接近基本情况.我们来看一个非常简单的例子:

def countdown(n)
  return if n.zero? # base case
  puts n
  countdown(n-1)    # getting closer to base case 
end               

countdown(5)
5
4
3
2
1

使用递归可以非常优雅地表达一些问题,例如,以递归方式描述了许多数学函数.

Answer 2

要了解递归,首先需要了解递归.

现在,严肃地说,递归函数是一个自我调用的函数.这种结构的一个典型例子是斐波那契序列:

def fib(n)
  return n if (0..1).include? n
  fib(n-1) + fib(n-2) if n > 1
end

使用递归函数可以为您提供强大的功能,同时还具有很多的责任性(双关语意),并且存在一些风险.例如,如果你的递归太大,你可能最终会出现堆栈溢出(我正在滚动):-)

Answer 3

Ruby on Rails示例：

递归将生成父母父母的数组

a/m/document.rb

class Document < ActiveRecord::Base

  belongs_to :parent, class_name: 'Document'

  def self.get_ancestors(who)
    @tree ||= []
    # @tree is instance variable of Document class object not document instance object
    # so: Document.get_instance_variable('@tree')

    if who.parent.nil?
      return @tree
    else
      @tree << who.parent
      get_ancestors(who.parent)
    end
  end

  def ancestors
    @ancestors ||= Document.get_ancestors(self)
  end

end

控制台：

d = Document.last
d.ancestors.collect(&:id)
# => [570, 569, 568] 

https://gist.github.com/equivalent/5063770