continuazioni Può essere usato come un sostituto per la ricorsione?

Question

La seguente funzione genera un 'livello di strato troppo in profondità (SystemStackError)' per n = 5000

def factorial(n)
  n == 0 ? 1 : factorial(n -1) * n
end

C'è un modo per evitare questo errore utilizzando continuazioni / callcc?

Nota:

So che questo può essere attuato senza ricorsione. per es.

def factorial2(n)
  (1..n).inject(1) {|result, n| result * n } 
end

Answer 1

Certo. Continuazioni possono fare nulla! Tuttavia, si finirà per reinventare una delle due cose: un loop o una chiamata di funzione. Sulla mia macchina, che fa l'ottimizzazione tail-call per impostazione predefinita, la ricorsione di coda con la chiamata / cc non ottenere ottimizzato. Il programma impantana rapidamente verso il basso, come ogni callcc cattura a quanto pare l'intero stack di chiamate. Tale codice viene rotto, ecco un ciclo di chiamata / cc:

def fact( n )
    (n, f, k) = callcc { |k| [ n, 1, k ] }
    if ( n == 0 ) then return f
    else k.call n-1, n*f, k
    end
end

Nota. in precedenza avevo dimenticato quella chiamata / cc non è solo l'avvio di una catena di continuazione-passing e sono confuso circa la necessità di ricorsione, quindi i commenti qui sotto

Answer 2

È possibile attivare l'ottimizzazione della coda-chiamata con tailcall_optimize :factorial, preso da qui .

class Class
  def tailcall_optimize( *methods )
    methods.each do |meth|
      org = instance_method( meth )
      define_method( meth ) do |*args|
        if Thread.current[ meth ]
          throw( :recurse, args )
        else
          Thread.current[ meth ] = org.bind( self )
          result = catch( :done ) do
            loop do
              args = catch( :recurse ) do
                throw( :done, Thread.current[ meth ].call( *args ) )
              end
            end
          end
          Thread.current[ meth ] = nil
          result
        end
      end
    end
  end
end

questo post interessante su come determinare se la ricorsione in coda è attivato.

Answer 3

Il problema è che la funzione restituisce factorial(n -1) * n che è un'espressione e nessuna singola chiamata ricorsiva. Se si riescono ad avere solo la chiamata di funzione nella dichiarazione di ritorno, la funzione viene chiamata coda ricorsiva , e un buon compilatore / interprete (non sono sicuro se Ruby è in grado di farlo) può fare un po ' ottimizzazioni per evitare l'utilizzo dello stack.

Tale funzione ricorsiva in coda potrebbe assomigliare a questo, ma si prega di notare che io non sono un programmatore Ruby, quindi sono né abituato alla sintassi, né alle caratteristiche dell'interprete. Ma si potrebbe essere in grado di provare da soli:

def factorial(n, result=1)
    n == 0 ? result : factorial(n-1, result * n)
end