再帰とは何ですか？どのように機能しますか？

Question

誰かが正確な再帰が何であるかを説明してもらえますか？私は再帰に頼っている長いコードスニペットに遭遇し、それは私を混乱させました（私は今それを失ってしまいました。

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 

再帰関数を使用すると、あなたに大きな力を与えるが、またresponsabilityの多くが付属しています（しゃれが意図し）、それはいくつかのリスクを提示します。たとえば、再帰が大きすぎると、スタックオーバーフロー（私はロール状になります）になる可能性があります:-)

Answer 3

通常、再帰は自分自身を呼び出すメソッドですが、遭遇したのは再帰構造、つまり自分自身を参照するオブジェクトでした。 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この種の問題については、数年前の再帰的構造の比較について述べています。

Answer 4

ルビーレール例で：

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

：

再帰は、親の親

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 

コンソールのアレイを生成します

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