Quali metodi ci sono per evitare uno stack overflow in un algoritmo ricorsivo?

Ottimizzazione delle chiamate tail è presente in molte lingue e compilatori. In questa situazione, il compilatore riconosce una funzione del modulo:

int foo(n) {
  ...
  return bar(n);
}

Qui, la lingua è in grado di riconoscere che il risultato che viene restituito è il risultato di un'altra funzione e di modificare una chiamata di funzione con un nuovo stack frame in un salto.

Renditi conto che il classico metodo fattoriale:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

è non chiamata di coda ottimizzabile a causa dell'ispezione necessaria al reso. ( Esempio di codice sorgente e output compilato )

Per rendere questa chiamata di coda ottimizzata,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

Compilare questo codice con gcc -O2 -S fact.c (il -O2 è necessario per abilitare l'ottimizzazione nel compilatore, ma con più ottimizzazioni di -O3 diventa difficile per un essere umano leggere ...)

_fact(int, int):
    cmpl    $1, %edi
    movl    %esi, %eax
    je  .L2
.L3:
    imull   %edi, %eax
    subl    $1, %edi
    cmpl    $1, %edi
    jne .L3
.L2:
    rep ret

( Esempio di codice sorgente e output compilato )

Si può vedere nel segmento .L3 , il jne piuttosto che un call (che fa una chiamata di subroutine con un nuovo frame dello stack).

Si noti che questo è stato fatto con l'ottimizzazione delle chiamate di C. Tail in Java è difficile e dipende dall'implementazione della JVM (detto ciò, non ho visto nessuno che lo faccia, perché è difficile e implica il modello di sicurezza Java richiesto richiede stack frame - che è ciò che evita TCO) - tail-recursion + java e tail-recursion + optimization sono buoni set di tag da sfogliare. Potresti trovare altre lingue JVM in grado di ottimizzare meglio la ricorsione della coda (prova clojure (che richiede ricorrere per ottimizzare le chiamate tail), o scala).

Detto questo,

C'èunacertagioianelsaperechehaiscrittoqualcosagiusto-nelmodoidealeincuipuòesserefatto.
_{^{Eora vado a prendere dello scotch e metto un po 'di elettronica tedesca ...}}

Alla domanda generale di "metodi per evitare uno stack overflow in un algoritmo ricorsivo" ...

Un altro approccio è includere un contatore di ricorsione. Questo è più utile per rilevare loop infiniti causati da situazioni al di fuori del proprio controllo (e scarsa codifica).

Il contatore di ricorsione assume la forma di

int foo(arg, counter) {
  if(counter > RECURSION_MAX) { return -1; }
  ...
  return foo(arg, counter + 1);
}

Ogni volta che si effettua una chiamata, si incrementa il contatore. Se il contatore diventa troppo grande, sbagli (qui, solo un ritorno di -1, anche se in altre lingue potresti preferire lanciare un'eccezione). L'idea è di evitare che accadano cose peggiori (errori di memoria insufficienti) quando si fa una ricorsione molto più profonda del previsto e probabilmente un ciclo infinito.

In teoria, non dovresti averne bisogno. In pratica, ho visto un codice scritto male che ha colpito questo a causa di una moltitudine di piccoli errori e cattive pratiche di codifica (problemi di concorrenza multithread in cui qualcosa cambia qualcosa al di fuori del metodo che fa entrare un altro thread in un ciclo infinito di chiamate ricorsive).

Usa l'algoritmo giusto e risolvi il problema giusto. In particolare per la congettura di Collatz, appare che stai cercando di risolverlo nel modo xkcd :

Staiiniziandoconunnumeroefacendounattraversamentodialberi.Questoportarapidamenteaunospaziodiricercamoltoampio.Unacorsarapidapercalcolareilnumerodiiterazioniperirisultatidellarispostacorrettaincirca500passaggi.Questonondovrebbeessereunproblemaperlaricorsioneconunpiccolostackframe.

Pursapendochelasoluzionericorsivanonèunabruttacosa,bisognaancherendersicontochemoltevoltelasoluzioneiterativa è migliore . Un certo numero di modi per avvicinarsi alla conversione di un algoritmo ricorsivo in uno iterativo può essere visto su Stack Overflow all'indirizzo Modo per passare dalla ricorsione all'iterazione .

Tieni presente che l'implementazione del linguaggio deve supportare l'ottimizzazione della ricorsione in coda. Non penso che i principali compilatori java lo facciano.

Memoizzazione significa che ricordi il risultato di un calcolo anziché ricalcalo ogni volta, come:

collatz(i):
    if i in memoized:
        return memoized[i]

    if i == 1:
        memoized[i] = 1
    else if odd(i):
        memoized[i] = 1 + collatz(3*i + 1)
    else
        memoized[i] = 1 + collatz(i / 2)

    return memoized[i]

Quando calcoli ogni sequenza in meno di un milione, ci sarà molta ripetizione alla fine delle sequenze. Memoization lo rende una rapida ricerca hash per i valori precedenti invece di dover rendere lo stack sempre più profondo.

Sono sorpreso che nessuno abbia menzionato ancora trampolino . Un trampolino (in questo senso) è un loop che invoca in modo iterativo le funzioni thunk-return (continuation passing style) e può essere usato per implementare chiamate di funzione ricorsive in una langauge di programmazione stack-oriented.

Questa domanda StackOverflow fornisce maggiori dettagli sulle varie implementazioni del trampolino in Java: Gestione di StackOverflow in Java per Trampoline

Se stai utilizzando un linguaggio e un compilatore che riconoscono le funzioni ricorsive della coda e le gestisce correttamente (cioè "sostituisce il chiamante in posizione con il callee "), quindi sì, la pila non dovrebbe crescere senza controllo. Questa ottimizzazione riduce essenzialmente un metodo ricorsivo a uno iterativo. Non credo che Java faccia questo, ma so che Racket fa.

Se segui un approccio iterativo, piuttosto che un approccio ricorsivo, stai rimuovendo gran parte della necessità di ricordare da dove provengono le chiamate, e praticamente eliminando la possibilità di un overflow dello stack (da chiamate ricorsive comunque).

La memoizzazione è ottima e consente di ridurre il numero complessivo di chiamate di metodo cercando i risultati precedentemente calcolati in una cache, dato che il calcolo complessivo comporterà calcoli ripetuti più piccoli. Questa idea è ottima - è anche indipendente dal fatto che tu stia utilizzando un approccio iterativo o ricorsivo.

potresti creare un'enumerazione che sostituirà la ricorsione ... ecco un esempio per il calcolo della facoltà che lo fa ... (non funzionerà con i numeri grandi come ho usato solo a lungo nell'esempio: -))

public class Faculty
{

    public static IEnumerable<long> Faculties(long n)
    {
        long stopat = n;

        long x = 1;
        long result = 1;

        while (x <= n)
        {
            result = result * x;
            yield return result;
            x++;
        }
    }
}

anche se questa non è memoization, in questo modo annullerai uno stack overflow

Modifica

Mi dispiace se ho fatto arrabbiare qualcuno di voi. La mia unica intenzione era mostrare un modo per evitare un eccesso di stack. Probabilmente avrei dovuto scrivere un esempio di codice completo invece di un piccolo frammento di un estratto di codice scritto rapidamente e approssimativo.

Il seguente codice

• evita la ricorsione mentre utilizzo i valori richiesti in modo iterativo.
• include la memoizzazione poiché i valori già calcolati vengono memorizzati e recuperati se già calcolati
• include anche un cronometro, quindi puoi vedere che la memoizzazione funziona correttamente

... umm ... se lo esegui assicurati di impostare la finestra della shell di comando per avere un buffer di 9999 righe ... il solito 300 non sarà sufficiente per scorrere i risultati del programma qui sotto. .

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.Timers;

namespace ConsoleApplication1
{
    class Program
    {
        static Stopwatch w = new Stopwatch();
        static Faculty f = Faculty.GetInstance();

        static void Main(string[] args)
        {
            Out(5);
            Out(10);
            Out(-5);
            Out(0);
            Out(1);
            Out(4);
            Out(29);
            Out(30);
            Out(20);
            Out(10000);
            Out(20000);
            Out(19999);
            Console.ReadKey();
        }

        static void Out(BigInteger n)
        {
             try
            {
                w.Reset();
                w.Start();
                var x = f.Calculate(n);
                w.Stop();
                var time = w.ElapsedMilliseconds;
                Console.WriteLine(String.Format("{0} ({2}ms): {1}", n, x, time));
            }
            catch (ArgumentException e)
            {
                Console.WriteLine(e.Message);
            }

            Console.WriteLine("\n\n");
       }
    }

Dichiaro   * 1 variabile statica "istanza" nella classe Faculty a un negozio un singleton. In questo modo finché il tuo programma è in esecuzione, ogni volta che ottieni "GetInstance ()" della classe ottieni l'istanza che ha memorizzato tutti i valori già calcolati.   * 1 SortedList statico che conterrà tutti i valori già calcolati

Nel costruttore aggiungo anche 2 valori speciali della lista 1 per gli ingressi 0 e 1.

    public class Faculty
    {
        private static SortedList<BigInteger, BigInteger> _values; 
        private static Faculty _faculty {get; set;}

        private Faculty ()
        {
            _values = new SortedList<BigInteger, BigInteger>();
            _values.Add(0, 1);
            _values.Add(1, 1);
        }

        public static Faculty GetInstance() {
            _faculty = _faculty ?? new Faculty();
            return _faculty;
        }

        public BigInteger Calculate(BigInteger n) 
        {
            // check if input is smaller 0
            if (n < 0)
                throw new ArgumentException(" !!! Faculty is not defined for values < 0 !!!");

            // if value is not already calculated => do so
            if(!_values.ContainsKey(n))
                Faculties(n);

            // retrieve n! from Sorted List
            return _values[n];
        }

        private static void Faculties(BigInteger n)
        {
            // get the last calculated values and continue calculating if the calculation for a bigger n is required
            BigInteger i = _values.Max(x => x.Key),
                           result = _values[i];

            while (++i <= n)
            {
                CalculateNext(ref result, i);
                // add value to the SortedList if not already done
                if (!_values.ContainsKey(i))
                    _values.Add(i, result);
            }
        }

        private static void CalculateNext(ref BigInteger lastresult, BigInteger i) {

            // put in whatever iterative calculation step you want to do
            lastresult = lastresult * i;

        }
    }
}

Come per Scala, puoi aggiungere l'annotazione @tailrec a un metodo ricorsivo. In questo modo, il compilatore assicura che l'ottimizzazione della chiamata di coda ha effettivamente avuto luogo:

Quindi questo non verrà compilato (fattoriale):

@tailrec
def fak1(n: Int): Int = {
  n match {
    case 0 => 1
    case _ => n * fak1(n - 1)
  }
}

il messaggio di errore è:

scala: could not optimize @tailrec annotated method fak1: it contains a recursive call not in tail position

D'altra parte:

def fak3(n: Int): Int = {
  @tailrec
  def fak3(n: Int, result: Int): Int = {
    n match {
      case 0 => result
      case _ => fak3(n - 1, n * result)
    }
  }

  fak3(n, 1)
}

compila e ha luogo l'ottimizzazione delle chiamate tail.

Una possibilità che non è stata ancora menzionata è quella di avere una ricorsione, ma senza usare uno stack di sistema. Ovviamente puoi anche scavalcare il tuo heap, ma se il tuo algoritmo ha davvero bisogno di tornare indietro in una forma o nell'altra (perché usare la ricorsione del tutto altrimenti?), Non hai scelta.

Esistono implementazioni stackless di alcune lingue, ad es. Python senza pila .

Un'altra soluzione sarebbe quella di simulare il proprio stack e non fare affidamento sull'implementazione del compilatore + runtime. Questa non è una soluzione semplice né rapida, ma teoricamente otterrai StackOverflow solo quando non hai memoria.