DOMANDA Programmi con ricorsione C++

[MPG]

UN array di 7 elementi va da 0 a 6 quindi n-1
sta di fatto che ho trovato entrambe le soluzioni in due siti esteri (quando ho dubbi faccio ricerca per capire meglio)
Una qui (mi pare un sito affidabile):
https://www.geeksforgeeks.org/recursive-programs-to-find-minimum-and-maximum-elements-of-array/
Scusa mi dirai che è orribile ma almeno dimmi come lo faresti tu.
Sicuramente funziona , risulta subito 45 con n=7 , pero' ripeto dimmi come lo faresti tu.
Grazie.

 

[rodhellas]

UN array di 7 elementi va da 0 a 6 quindi n-1
sta di fatto che ho trovato entrambe le soluzioni in due siti esteri (quando ho dubbi faccio ricerca per capire meglio)
Una qui (mi pare un sito affidabile):
https://www.geeksforgeeks.org/recursive-programs-to-find-minimum-and-maximum-elements-of-array/
Scusa mi dirai che è orribile ma almeno dimmi come lo faresti tu.
Sicuramente funziona , risulta subito 45 con n=7 , pero' ripeto dimmi come lo faresti tu.
Grazie.

Spoiler

//usando il tuo programma di base
int massimo(int A[], int n, int max)
{
      if (n == -1)
        return max;
     if(A[n] > max)
        return massimo(A, n-1, A[n]);
    return massimo(A, n-1, max);
}

int main()
{
    int A[] = {1, 4, 45, 6, -50, 10, 2};
    int n=7;
    cout <<  massimo(A, n-2, A[n-1]);     //supponendo l'array con almeno un elemento
    return 0;
}

 

[MPG]

Scusami puoi cortesemente spiegarmi i due return e il cout in modo che riesco a comprendere bene come funzionano? Grazie.

 

[rodhellas]

Scusami puoi cortesemente spiegarmi i due return e il cout in modo che riesco a comprendere bene come funzionano? Grazie.

Il primo return ritorna il massimo trovato dopo aver passato tutti i valori dell' array. Gli altri due semplicemente richiamano la funzione aggiornando il massimo trovato fino ad allora. E il cout stampa il massimo ritornato dopo tutti i passi ricorsivi.

 

[MPG]

Caspita non ci arrivo fino in fondo..
Quell'n-2?

 

[rodhellas]

Il tuo primo massimo è l'ultimo elemento (n-1). Il prossimo elemento da confrontare è n-2

 

[MPG]

Scusate riapro questo thread per il massimo numero in un array usando ricorsione .
Vorrei capire quella spiegazione trovata online in allegato.
In pratica parto che 2 (n-1) è il massimo valore e poi vado a controllare gli altri.
Ora perchè nel confronto con 5,1 mi mette max (1, array_max([5], 1)) ??

int massimo(int A[], int n)
{
      if (n == 1)
        return A[0];
    return max(A[n-1], massimo(A, n-1));
}

int main()
{
    int A[] = {1, 4, 45, 6, -50, 10, 2};
    int n=7;
    cout <<  massimo(A, n);
    return 0;
}

 

[rodhellas]

Ora perchè nel confronto con 5,1 mi mette max (1, array_max([5], 1)) ??

Perchè ti è rimasto solo 5 nell'array ([5]) e quindi ha lunghezza 1. Cosi array_max, dato n=1, ritornerà array[0] ovvero 5.

 

[Zeus Giove]

A parte che non capisco come mai cerchi ancora di fare azioni in maniera ricorsiva che personalmente non Capisco appieno, preferendo quella iterativa, e che credo che se non hai ancora capito come si lavora con la ricongiunzione dopo un anno che Ci sbatti contro la testa non credo lo capirai mai ( se le premesse sono buone visto che ti porti questi problemi Addirittura in vacanza)

Comunque sia i dati che devi passare alla funzione non sono due, ma 3:
1) il puntatore al primo elemento da analizzare
2) il numero di elementi restanti
3) il valore massimo fino ad adesso trovato

Nel corpo della funzione comincia a prevedere la formula di uscita:
Se il numero di elementi da analizzare è minore o uguale a 0, la funzione deve ritornare il massimo valore fino ad adesso trovato

In tutti gli altri casi la funzione deve ritornare il ritorno della stessa con i parametri Cambiati nel seguente modo:
Il puntatore a primo elemento+1
Numero elementi restanti-1
Massimo trovato=max( Massimo trovato, elemento corrente)

 

[MPG]

Io volevo analizzare bene questo
tenendo conto di questo:
return max(A[n-1], massimo(A, n-1));

:
max (2, max (1, array_max([5], 1))
il 2 deriva da n-1
l' 1 che compare dopo il max e la ( ha quindi significato che è rimasto 1 solo numero quindi ?

Comunque se in sesercizi di ricorsione come divisione, somma e fattoriale sono riuscito a capire in questa procedura dell'allegato faccio fatica a capire i passaggi .
Potete spiegarmeli esattamente citando ogni passaggio?
Prendendo questo:
return max(A[n-1], massimo(A, n-1))
io non riuscirei a spiegare come è stato spiegato nell'allegato quello che avviene.
Ho ripresto questo thread perchè alla fine non è stato bene chiarito a fine scuola e permane la mia difficoltà in materia....

 

[fabio93]

La funzione prende in input due parametri: l'array e la sua lunghezza. Ovviamente se la lunghezza è 1 (l'array contiene solo un elemento), il massimo coincide con l'unico valore presente nell'array, e questo è il caso base.
Altrimenti viene chiamata la funzione max, che restituisce il massimo tra due numeri, con i seguenti argomenti: l'ultimo elemento dell'array (A[n-1]) e il massimo degli elementi dell'array escludendo l'ultimo elemento (array_max(A, n-1), qui avviene la ricorsione). A ogni chiamata ricorsiva n diminuisce, perciò alla fine si ricade nel caso base e le chiamate ricorsive terminano.

Nell'esempio con l'array A=[5,1,9,2] vengono effettuate le seguenti chiamate:
1) array_max(A, 4) -> poiché la lunghezza è maggiore di 1 chiama max(2, array_max(A, 3))
2) array_max(A, 3) -> chiama max(9, array_max(A, 2))
3) array_max(A, 2) -> chiama max(1, array_max(A, 1))
4) array_max(A, 1) -> caso base, restituisce 5, l'unico elemento presente nell'array (o meglio, l'unico considerato avendo indicato come lunghezza 1)
Si risale:
3) array_max(A, 2) restituisce max(1, array_max(A, 1)) = max(1, 5) = 5
2) array_max(A, 3) restituisce max(9, array_max(A, 2)) = max(9, 5) = 9
1) array_max(A, 4) restituisce max(2, array_max(A, 3)) = max(2, 9) = 9
Perciò il massimo è 9.