[Algoritmi] Quanto spazio consuma una ricorsione?

[absinth]

Ciao a tutti! Vi chiedo per favore di aiutarmi con un dubbio. Sto leggendo un po' su internet ma non capisco bene quanto spazio consuma un algoritmo ricorsivo. Ad esempio ho appena fatto un algoritmo ricorsivo che mi da la dimensione della massima sottostringa palindrome di una parola che se date un'occhiata è tipo un forma tipo un albero di N^2 nodi "chiamate", ma la profondità delle foglie è N. Però so che ha uno stack interno.. insomma di solito esiste un modo per capire quanto spazio richiede una ricorsione?
(per chi volesse dare un'occhiata anche al codice:)

int palindrome(char word[], int i, int j, int count)
{
	if(j-i==1)
	{
		if(word[i]==word[j])
			return count+2;
		return 0;
	}
	int dim = 0;
	if(word[j]==word[i])
		dim = count+2;
	int left = palindrome(word, i, j-1, dim);
	int right = palindrome(word, i+1, j, dim);
	if(left>right)
		return left;
	return right;
}

[apatriarca]

Quando fai una chiamata ricorsiva, tutte le variabili locali sono contenute nello stack che quindi crescerà ad ogni successiva chiamata ricorsiva. La quantità di memoria utilizzata sarà quinid in generale proporzionale alla "profondità" massima raggiunta durante la ricorsione.

[absinth]

Grazie mille!!

[absinth]

Mi è venuta in mente un'altra domanda al momento che non centra però è importante: questa mia versione ricorsiva si può considerare come dynamic programming o di solito per dynamic si intende anche l'utilizzo di matrici per salvare certi dati o altre strutture per tecniche tipo "memoization" ?