esercizi sulla ricorsione

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