Se le strutture dati come alberi e determinati tipi (ordinamento rapido, ordinamento di unione) funzionano utilizzando algoritmi ricorsivi e algoritmi ricorsivi occupano molto spazio di memoria nello stack e possono funzionare solo su set di dati limitati (se non lo sono) porteremo allo stackoverflow), quindi come mai gli alberi e le specie sopra menzionate sono stati usati praticamente per gestire grandi insiemi di dati. Non porterebbe allo stackoverflow?
La tua domanda è troppo ampia e troppo generica. Riguardo alle strutture dati e agli algoritmi, dovresti davvero leggere un libro su di loro, come Introduzione agli algoritmi (aka CLRS)
recursive algorithms take up a lot of memory space in the stack
Questo non è sempre vero (e di solito falso).
Innanzitutto, lo stack di chiamate non è così piccolo su computer ( computer portatili , desktop , server) che utilizzano i soliti sistemi operativi (Windows, Linux , Android, MacOSX) nel 2018. Come regola generale, può richiedere uno o pochi megabyte (che non è piccolo: un tipico libro tascabile contiene meno di un milione di caratteri e potrebbe quasi adattarsi a esso, la Sacra Bibbia regge circa quattro milioni caratteri ed è un lungo libro da leggere, anche romanzi molto lunghi come Guerra e pace non sono molto più grandi e probabilmente più piccoli).
Su microcontrollori a buon mercato come quelli all'interno del mouse, della tastiera o dell'appliance o di un Arduino , lo stack di chiamate è più piccolo: kilobyte o anche poche centinaia di byte; ma la RAM è anche più piccola, la frequenza di clock è più lenta (MHz).
In secondo luogo, e soprattutto, buoni algoritmi ricorsivi e strutture dati (si pensi agli alberi, in particolare a alberi binari autobilancianti ) consumano una profondità di ricorsione che spesso segue una crescita logaritmica . Quindi, ad esempio, raddoppiando la dimensione della struttura dei dati si aumenterebbe la profondità di ricorsione di un importo piccolo, fisso.
Ovviamente tutto quanto sopra è approssimativo e sfocato (come la tua domanda). Alcuni algoritmi ricorsivi sono lineari, ma di solito non li usano (almeno non su grandi set di dati). Ricorda inoltre ricorsione in coda .
Ovviamente, leggi ulteriori informazioni sulla complessità temporale .
Wouldn't it lead to stackoverflow?
In pratica no, se la crescita è logaritmica. Ricorda che 2 64 è davvero un numero enorme (più del numero di atomi nel tuo corpo), ma 64 non lo è. Tieni presente ordine di grandezza .
Tenere presente che un buon programmatore scrive solo due o tre dozzine di righe di codice ogni anno, o solo un megabyte o due di codice sorgente ogni anno. E un tipico computer può contenere migliaia di byte in più nella sua RAM (ad esempio la maggior parte dei computer ha più di un gigabyte di RAM nel 2018)
Non ho spazio o tempo per spiegare di più, ma voglio dare l'impressione che la programmazione e l'informatica siano difficili, e hai bisogno di anni per imparare it. Quindi ottenere una laurea in CS richiede tempo, ma vale la pena.
Leggi altre domande sui tag recursion data-structures memory memory-usage sorting