esercizi sulla ricorsione

[jimbo0]

salve, mi sono reso conto che sono più che arrugginito su quest'argomento..non mi viene naturale pensare ad una soluzione ricorsiva ad un problema postomi.
Cercando sul web si trovano solo esercizi e spiegazioni banali, io non cerco quello, so cos'è la ricorsione e come si applica, cerco degli esercizi un po' di avanzati, per abituarmi a pensare appunto in maniera ricorsiva, potete improvvisarli anche voi (per un programmatore è semplicissimo) magari usando anche qualche libreria standard di java tipo arraylist, stack o queue.
help mi?

[andbin]

cerco degli esercizi un po' di avanzati, per abituarmi a pensare appunto in maniera ricorsiva, potete improvvisarli anche voi

Bene, allora prova a scrivere una classe con un metodo ricorsivo per scansionare in "profondità" un albero di directory data una directory radice. Questa è una delle cose che si fa tipicamente in ricorsione. Fai ad esempio in modo da ottenere alla fine un List<File> con tutti i file (non le directory) trovati.

Una cosa che all'uso sarebbe es.:

DirTreeScanner dts = new DirTreeScanner();
List<File> files = dts.collectFiles("C:/blabla");

[OmarCore93]

Che strutture dati conosci? Se conosci anche gli alberi ne ho un sacco di esercizi ricorsivi sugli alberi.

[jimbo0]

si sto studiando gli alberi, ed in effetti anche se tempo fa programmavo agevolmente con file e db l'esercizietto di andbin mi è astruso perché dovrei riprendere dalla doc File e classi annesse. esercitarmi sugli alberi mi è più utile ora.

[OmarCore93]

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.

[Scara95]

Scrivi un implementazione delle liste scrivendo ogni operazione ricorsivamente:
-insert
-delete
-map
-fold
-reverse
-zip
-append
-sort (quicksort (per implementarlo devi prima implementare altre funzioni))

[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!

[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.

calma ragazzi io sono ancora a questo, che effettivamente si avvicina molto a quello che sto studiando.
purtroppo la complessità ancora non l'ho studiata (lacuna mia, nel corso di studi ovviamente viene prima la complessità e poi lo studio delle strutture dati).
Ed a proposito del fatto che non so pensare ricorsivamente, non ho idea di come risolverlo ad esempio io penserei alla necessità di una variabile esterna "max" da mantenere fuori dalla funzione, ma credo che tu sia di parere diverso
un paio di suggerimenti e vediamo se ci arrivo

ps: per inciso il fatto che il tuo nick sia "93" non fa altro che infagianarmi ulteriormente