esercizi sulla ricorsione

[jimbo0]

Un esercizio:
Dato un albero binario in cui ogni nodo è bianco o nero (identificali come vuoi), un sottoalbero monocolore è un sottoalbero avente tutti i nodi dello stesso colore: scrivere un algoritmo che calcola la dimensione massima di un sottoalbero monocolore nell'albero, dove per dimensione si intende la quantità di nodi del sottoalbero.
Non so se sai cos'è la complessità computazionale, fatto sta che puoi farlo in tempo O(n), se non sai cos'è fallo pure senza tenere conto dell'efficienza.

ho scritto questa roba che almeno dovrebbe contare le occorrenze del colore (so che non è quello che chiede il problema posto )
ho usato le implementazioni usate nel corso ma credo sia tutto comprensibile (BTPosition<E> è un nodo dell'albero che usa tipo generico E, Position è l'interfaccia implementata da BTPosition).
il problema qui è che num viene azzerato ad ogni ricorsione credo quindi?

	public int getMaxSubtree(E color, Position<E> c){
		BTPosition<E> cc = checkPosition(c);
		int num=0;
		if(hasLeft(cc)) { 
			if(color==cc.element()) num+=getMaxSubtree(color, left(cc));			
			getMaxSubtree(color, left(cc));
			}
		if(hasRight(cc)){
			if(color==cc.element()) num+=getMaxSubtree(color, left(cc));
			getMaxSubtree(color, left(cc));
		}
		return num;
	}

[OmarCore93]

Vabbè il Fold e il Quicksort li deve implementare ricorsivi per forza, grazie.

[Scara95]

Vabbè il Fold e il Quicksort li deve implementare ricorsivi per forza, grazie.

Ma da quando il fold di una lista deve per forza essere ricorsivo?!
pseudocodice iterativo:

fold(acc, fun, list)
  for n in list
    acc = fun(acc, n)
  return acc

Parimenti il quicksort non necessita di essere ricorsivo, anche se la cosa si complica...
Comunque ricordiamoci sempre che ogni algoritmo ricorsivo può essere scritto linearmente con l'uso di cicli e/o stack e viceversa

[OmarCore93]

Ma da quando il fold di una lista deve per forza essere ricorsivo?!
pseudocodice iterativo:

fold(acc, fun, list)
  for n in list
    acc = fun(acc, n)
  return acc

Parimenti il quicksort non necessita di essere ricorsivo, anche se la cosa si complica...
Comunque ricordiamoci sempre che ogni algoritmo ricorsivo può essere scritto linearmente con l'uso di cicli e/o stack e viceversa

Vabbè forse sul Fold ho sbagliato, è che a me lo hanno insegnato ricorsivo ed effettivamente almeno il Foldr si presta molto bene ricorsivo. Per quanto riguarda il Quicksort, se parli proprio della versione fatta da Hoare, beh, è ricorsivo, è un algoritmo di ordinamento ricorsivo e mica me lo sto inventando io!