[c] ricorsione

[white05]

Come trovare il minimo di un array 1D con metodo ricorsivo?
Ho provato varie strade ma credo di essere giunto a qualche cosa di troppo complesso! Deve esserci sicuramente un metodo MOLTO più facile!

[andbin]

Originariamente inviato da white05

Come trovare il minimo di un array 1D con metodo ricorsivo?
Ho provato varie strade ma credo di essere giunto a qualche cosa di troppo complesso! Deve esserci sicuramente un metodo MOLTO più facile!

Scusa... perché usare la ricorsione quando basta un semplice ciclo for??

[marco.r]

Originariamente inviato da white05

Come trovare il minimo di un array 1D con metodo ricorsivo?
Ho provato varie strade ma credo di essere giunto a qualche cosa di troppo complesso! Deve esserci sicuramente un metodo MOLTO più facile!

qualcosa del genere:

int array_min( int* data, int length )
{
  return rec_min( data[0], data+1, length -1);
}

int rec_min( int x, int* data, int length )
{
  if (length == 0 )
    return x;
  x = min(x,data[0])
  return rec_min( x , data+1, length-1);
}

Che tra l'altro dovrebbe risultare tail-recursive.

[white05]

Scusa... perché usare la ricorsione quando basta un semplice ciclo for??

perché purtroppo quando le persone incompetenti chiedono di realizzare qualche cosa per dei corsi non si rendono conto che così non insegnano a programmare ma confondono solo le idee....

Che tra l'altro dovrebbe risultare tail-recursive.

tail-recursive significa???

Pensa che in realtà si dovrebbe creare una ricerca di minimo con ricorsione e approccio divide et impera...
assurdo da un punto di vista della logica della programmazione

[71104]

Originariamente inviato da white05

tail-recursive significa???

che si converte in un algoritmo iterativo con estrema naturalezza e semplicità

Pensa che in realtà si dovrebbe creare una ricerca di minimo con ricorsione e approccio divide et impera...

prova questa porcheria ma non ti fidare troppo, l'ho scritta in 2 secondi senza manco provare

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define F FunzioneTotalmenteImbecille

int FunzioneTotalmenteImbecille(int *Array, int Start, int End) {
    if (End == Start) {
        return Array[Start];
    }
    return MIN(F(Array, Start, Start + (End - Start) / 2),
        F(Array, Start + (End - Start) / 2 + 1, End));
}

assurdo da un punto di vista della logica della programmazione

concordo, e sono sinceramente contento per te che tu l'abbia capito: vuol dire che nonostante le assurde richieste dei professori, se gli studenti ci mettono del loro alla fine qualcosa in termini di preparazione la guadagnano lo stesso. intendiamoci, ovviamente sarebbe tutto più facile se i professori evitassero di andare controcorrente...

[71104]

ma perché non chiedi al tuo prof di farvi fare algoritmi che meritino realmente un approccio divide et impera? come ad esempio uno dei tanti algoritmi di ordinamento... -_-'

[andbin]

Originariamente inviato da white05

perché purtroppo quando le persone incompetenti chiedono di realizzare qualche cosa per dei corsi non si rendono conto che così non insegnano a programmare ma confondono solo le idee....

Purtroppo non posso fare altro che quotare quanto appena detto. Direi volentieri qualcos'altro sui professori ... ma è meglio se non lo faccio.


Ah, per il minimo di un array ci ho provato anche io. Ecco la "mia" soluzione:

int int_array_min (int *arr, int length)
{
    int min = *arr;

    if (length > 1)
        min = int_array_min (arr+1, length-1);

    return *arr < min ? *arr : min;
}

int main (void)
{
    int a[4] = { 12, 5, 7, 20 };
    int min;

    min = int_array_min (a, 4);

    return 0;
}

Non l'ho provata al 100% ma credo che sia ok.

[thebol]

Originariamente inviato da 71104

ma perché non chiedi al tuo prof di farvi fare algoritmi che meritino realmente un approccio divide et impera? come ad esempio uno dei tanti algoritmi di ordinamento... -_-'

e vero, ma è l'unico modo per forzare gli studenti a provare la programmazione ricorsiva.

anche se sarebbe meglio impararla su un linguaccio funzionale(io ho imparato su schema, e anche io all'epoca lo odiavo...)

[marco.r]

Originariamente inviato da 71104

che si converte in un algoritmo iterativo con estrema naturalezza e semplicità


prova questa porcheria ma non ti fidare troppo, l'ho scritta in 2 secondi senza manco provare

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define F FunzioneTotalmenteImbecille

int FunzioneTotalmenteImbecille(int *Array, int Start, int End) {
    if (End == Start) {
        return Array[Start];
    }
    return MIN(F(Array, Start, Start + (End - Start) / 2),
        F(Array, Start + (End - Start) / 2 + 1, End));
}

concordo, e sono sinceramente contento per te che tu l'abbia capito: vuol dire che nonostante le assurde richieste dei professori, se gli studenti ci mettono del loro alla fine qualcosa in termini di preparazione la guadagnano lo stesso. intendiamoci, ovviamente sarebbe tutto più facile se i professori evitassero di andare controcorrente...

L'approccio divide et impera qua non ti serve, l'array non è ordinato e devi *comunque* passare in rassegna tutti gli elementi . Se fai un paio di conti vedrai che all'incirca fai lo stesso numero di confronti. A voler essere pignoli, in questo modo accedi "a saltoni" alla memoria, col probabile risultato di rallentare l'afflusso dei dati alla cpu (soprattutto se l'array è piu' grande della cache del processore).

[marco.r]

Originariamente inviato da thebol

e vero, ma è l'unico modo per forzare gli studenti a provare la programmazione ricorsiva.

anche se sarebbe meglio impararla su un linguaccio funzionale(io ho imparato su schema, e anche io all'epoca lo odiavo...)

Concordo, una volta assimilata la ricorsione diventa piu' naturale e pure semplice da capire.
In questo caso pero' l'esempio non è dei migliori ([i]grazie[(i] anche alla scelta del C come linguaggio).

[71104]

Originariamente inviato da marco.r

L'approccio divide et impera qua non ti serve, [...]

l'ha detto lui che serve, è una richiesta dell'esercizio

[il_luridone]

io risolverei così

int
minimo (int *input, int p, int r)
{
  int q;     /* mediano attorno il quale dividiamo l'array */

  if ((r - p) > 0)
    {
      q = floor ((r - p) / 2);
      return MIN (minimo (input, p, p + q), minimo (input, p + q + 1, r));
    }
  else
    return input[p];
}

input è l'array di interi, p e r sono gli indici del primo e dell'ultimo elemento. Per esempio, se hai un array con tre interi, hai p = 0 e r = 2.

Se r - p > 0 allora hai più di un elemento nell'array e hai bisogno di spezzare il problema: q è il mediano inferiore dell'array e le due parti vengono passate a due chiamate ricorsive della funzione.

Se r - p == 0 allora l'array ha un solo elemento, che è banalmente il minimo dell'array.

Quando le ricorsioni spezzettano i sottoproblemi fino ad arrivare ad array di un elemento, la ricorsione finisce e i numeri ritornati vengono confrontati dalla macro MIN

#define     MIN(x,y)     ((x) < (y) ? (x) : (y))

che non è altro che un condizionale per selezionare il numero minore.

Questo è un semplice codice di test, se lo intitoli "min_ricorsivo.c" lo puoi compilare con "gcc -Wall -ansi -pedantic -lm -o min_ricorsivo min_ricorsivo.c"

#include <stdio.h>
#include <stdlib.h>
#include <math.h>


#define     MIN(x,y)     ((x) < (y) ? (x) : (y))


int
minimo (int *input, int p, int r)
{
  int q;

  if ((r - p) > 0)
    {
      q = floor ((r - p) / 2);
      return MIN (minimo (input, p, p + q), minimo (input, p + q + 1, r));
    }
  else
    return input[p];
}


int
main (int argc, char **argv)
{
  int i;
  int *input;

  input = (int *) malloc ((argc - 1) * sizeof (int));
  if (input == NULL)
    {
      perror ("errore malloc");
      exit (1);
    }


  if (argc == 1)
    {
      printf ("uso: min_ricorsivo <numeri interi>\n");
      printf ("i numeri interi devono essere separati da spazi.\n");
      exit (1);
    }

  for (i = 1; i < argc; i++)
    {
      input [i-1] = strtol(argv[i], (char **)NULL, 10);
      printf ("%d ", input [i - 1]);
    }

  printf ("\n");

  printf ("min = %d\n", minimo(input, 0, argc - 2));

  return 0;
}

Metti qualche numero come argomento a linea di comando e dovrebbe sputare il minimo. Per capire bene cosa succede aiuta sicuramente disegnare l'array di input su un foglio ed eseguire il programma passo passo con un debugger, controllando tutti i valori delle variabili e aggiornando di conseguenza il disegno.

Spero vada bene, l'ora è quella che è

[sars]

Originariamente inviato da white05

perché purtroppo quando le persone incompetenti chiedono di realizzare qualche cosa per dei corsi non si rendono conto che così non insegnano a programmare ma confondono solo le idee....



tail-recursive significa???

Significa che l'ultima istruzione della funzione e` la chiamata ricorsiva. Molti compilatori di linguaggi funzionali possono usarla per ottimizzare l'uso dello stack (non credo che ci siano compilatori c che lo fanno)

Pensa che in realtà si dovrebbe creare una ricerca di minimo con ricorsione e approccio divide et impera...
assurdo da un punto di vista della logica della programmazione

Delirio puro.
(primo post: saluti a tutti!)

[sars]

Originariamente inviato da marco.r

Concordo, una volta assimilata la ricorsione diventa piu' naturale e pure semplice da capire.
In questo caso pero' l'esempio non è dei migliori ([i]grazie[(i] anche alla scelta del C come linguaggio).

Comunque anche con un linguaggio funzionale nessuno userebbe mai la ricorsione per cercare il minimo in un vettore, in lisp:

(reduce #'min array)

[marco.r]

Originariamente inviato da 71104

l'ha detto lui che serve, è una richiesta dell'esercizio

Chiedo scusa, non l'avevo capito

[marco.r]

Originariamente inviato da sars

Comunque anche con un linguaggio funzionale nessuno userebbe mai la ricorsione per cercare il minimo in un vettore, in lisp:

(reduce #'min array)

Sicuro, se non altro perchè abbiamo funzioni di piu' alto livello già pronte . Il mio discorso era che, volendo scriversela, di solito la versione ricorsiva riesce ad essere piu' elegante e chiara della corrispondente iterativa, ma in questo caso è il contrario.

[sars]

Originariamente inviato da marco.r

Il mio discorso era che, volendo scriversela, di solito la versione ricorsiva riesce ad essere piu' elegante e chiara della corrispondente iterativa, ma in questo caso è il contrario.

Diciamo che dipende, certe cose sono piu` chiare con un loop, certe ricorsivamente.

[il_luridone]

A me non sembra tanto strano che la didattica insegni roba poco utile in pratica ma semplice concettualmente.

Capire un concetto nuovo come la ricorsione partendo da casi reali mi sembra controproducente. Una volta compreso il concetto grazie all'esempio banale e scolastico, si può procedere per gradi di difficoltà (come si fa sempre in ogni corso non solo informatico).

Poi sarà compito dello studente digerire il concetto elementare ed applicarlo ai casi veri.

[sars]

Originariamente inviato da il_luridone

A me non sembra tanto strano che la didattica insegni roba poco utile in pratica ma semplice concettualmente.

Capire un concetto nuovo come la ricorsione partendo da casi reali mi sembra controproducente. Una volta compreso il concetto grazie all'esempio banale e scolastico, si può procedere per gradi di difficoltà (come si fa sempre in ogni corso non solo informatico).

Poi sarà compito dello studente digerire il concetto elementare ed applicarlo ai casi veri.

E qual'e` lo scopo didattico di scrivere algoritmi inutilmente contorti?

[71104]

Originariamente inviato da sars

E qual'e` lo scopo didattico di scrivere algoritmi inutilmente contorti?

imparare la sofisticata tecnica della contorsione, anche detta yoga informatico; aiuta a ritrovare il benessere interiore del tuo software: diurifica, vivifica, slarga le vene, fa ca@are bene.