Qu'est-ce que la récursivité et comment ça fonctionne?

Quelqu'un pourrait-il expliquer ce qu'est exactement la récursivité est (et comment il fonctionne dans Ruby, si ce n'est pas trop demander). Je suis tombé sur un long extrait de code en s'appuyant sur la récursivité et il me troublait (je l'ai perdu maintenant, et ce n'est pas tout à fait pertinente).

  • comment est-il pas pertinent si c'est ce que vous avais confondu? Et la récursivité est un principe général dans le calcul qui peuvent être effectuées dans la plupart des langues, il n'est pas un concept spécifique à Ruby
InformationsquelleAutor omninonsense | 2011-06-20
  1. 61

    Une fonction récursive/appels à la méthode elle-même. Pour un algorithme récursif de résilier vous avez besoin d'une base de cas (par exemple, une condition où la fonction ne pas appeler récursivement) et vous devez également vous assurer que vous obtenez le plus proche de celui de la base de cas dans chaque appel récursif. Regardons un exemple très simple:

    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

    Certains problèmes peuvent être très élégamment exprimé avec la récursivité, e.g beaucoup de fonctions mathématiques sont décrits de manière récursive.

    • Bien expliqué!
    InformationsquelleAutor Michael Kohl
  2. 33

    Pour comprendre la récursivité, vous devez d'abord comprendre la récursivité.

    Maintenant, sur une note plus sérieuse, une fonction récursive est une fonction qui s'appelle elle-même. Un exemple classique de cette construction est la suite de fibonacci:

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

    À l'aide de fonctions récursives vous donne un grand pouvoir, mais est également livré avec un lot de responsability (pun intended) et il présente un certain risque. Par exemple, vous pourriez vous retrouver avec des débordements de pile (je suis sur un rouleau) si votre ressemble est trop grand 🙂

    • Vous avez raison @changeloge. Il y a longtemps, tout en jouant avec de la cisr je n'ai pas obtenu le résultat pour les plus de 5 minutes en utilisant le code ci-dessus avec de gros séquence de Fibonacci "55". J'ai trouvé de Hachage est plus rapide comme: fibonacci = Hash.nouveaux{ |h k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }
    InformationsquelleAutor changelog
  3. 4

    Ruby on Rails exemple:

    Récurrence générer tableau de parents de parents

    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

    console: 

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

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

    InformationsquelleAutor equivalent8
  4. 2

    Généralement la récursivité est sur la méthode appelant eux-mêmes, mais peut-être que vous avez rencontrées étaient structures récursives, c'est à dire les objets se référant à eux-mêmes. Ruby 1.9 gère ces vraiment bien:

    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

    Je trouve que la dernière ligne est tout à fait méchants; je blogué à propos de ce genre de problèmes avec une comparaison de structures récursives il y a quelques années.

    InformationsquelleAutor Marc-André Lafortune