Что такое рекурсия и как она работает?

Может кто-нибудь объяснить, что такое рекурсия (и как это работает в Ruby, если этого не слишком много, чтобы просить). Я натолкнулся на длинный фрагмент кода, полагающийся на рекурсию, и это смутило меня (я потерял его сейчас, и это не совсем актуально).

Ответ 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

Некоторые проблемы могут быть очень элегантно выражены с помощью рекурсии, например, многие математические функции описываются рекурсивным образом.

Ответ 2

Чтобы понять рекурсию, вам сначала нужно понять рекурсию.

Теперь, на серьезной ноте, рекурсивная функция - это функция, которая сама вызывает вызов. Один классический пример этой конструкции - последовательность фибоначчи:

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

Использование рекурсивных функций дает вам большую силу, но также обладает большой ответственностью (каламбур) и представляет определенный риск. Например, вы можете завершить переполнение стека (я нахожусь в рулоне), если ваша рекурсивность слишком велика: -)

Ответ 3

Ruby on Rails пример:

Рекурсия будет генерировать массив родителей родителей.

а/м/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

Ответ 4

Обычно рекурсия касается метода, вызывающего себя, но, возможно, вы столкнулись с рекурсивными структурами, то есть объектами, относящимися к себе. Ruby 1.9 отлично справляется с этим:

h = {foo: 42, bar: 666}
parent = {child: {foo: 42, bar: 666}}
h[:parent] = parent
h.inspect # => {:foo=>42, :bar=>666, :parent=>{:child=>{...}}}

x = []
y = [x]
x << y
x.inspect # => [[[...]]]
x == [x]  # => true

Я считаю, что последняя строка довольно злая; я blogged об этих проблемах со сравнением рекурсивных структур пару лет назад.