[C++] Implementazione funzione ricorsiva

[ireon]

Ragazzi, dovrei implementare una soluzione ricorsiva in grado di individuare il valore più piccolo contenuto in un array.

Però non ci riesco, la soluzione iterativa la implemento senza problemi, infatti il codice è il seguente:

int min (int a[], int size)

{

    int min_array = a[0];
    for (int i=1; i<size; i++)
    if (a[i]<a[0])
    min_array = a[i];

    return min_array;

}

Ma per la soluzione ricorsiva avrei qualche problema, qualcuno potrebbe aiutarmi?

[antotan]

Un piccolo appunto. La tua funzione non ritorna il minimo. Devi apportare una piccola modifica. Riesci ad individuare quale?

Test:

#include <stdio.h>

int min (int a[], int size)

{
    int min_array = a[0];
	int i;
    for (i=1; i<size; i++)
		if (a[i]<a[0])
			min_array = a[i];

    return min_array;

}

int main()
{
	int arr[] = {1,2,-1,0};
	printf("%d\n", min(arr, 4));
}

[ireon]

Si, l'ho copiata male, il codice giusto è questo:

int min (int a[], int size)

{

    int min_array = a[0];
    for (int i=1; i<size; i++)
    if (a[i]<min_array)
    min_array = a[i];

    return min_array;

}

Però tralasciando la soluzione iterativa, che non è quella che mi interessa in questo caso, come posso implementare la soluzione ricorsiva?

[ireon]

Ho provato a implementare la soluzione ricorsiva, ma con scarso successo, infatti non funziona e quando lancio l'eseguibile mi ritorna un numero casuale come minimo... Il codice l'ho scritto così:

#include<iostream>

using namespace std;



int min (int a[], int size)

{

    int minimo;
    int size2 = size-1;
    if (a[size2] < a[0])
    { a[0] = a[size2];
      minimo = a[0];
    }
     if (size2==1) return minimo;

    
    min (a, size2);

}


void print (int a[], int size)

{
    for (int i = 0; i < size; i++)

    cout << a[i] << endl;

}




int main()

{

int a[7];

a[0]= 102;
a[1]= 36;
a[2]= 100;
a[3]= 12;
a[4]= 32;
a[5]= 70;
a[6]= 82;


print (a,7);

cout << endl;

int minimo_elemento = min(a,7);

cout << minimo_elemento << endl;


return 0;

}

In pratica nel corpo della funzione ho dichiarato una variabile intera minino, poi ho dichiarato una variabile intera size2 uguale a size-1, ovvero all'ultimo elemento dell'array, quindi se l'ultimo elemento è minore del primo, il minimo è uguale all'ultimo elemento, che metto nella prima posizione dell'array, poi controllo se l'array è stato scorso tutto con la condizione if (size2==1) return minimo; che mi dovrebbe restituire il minimo quando tutti i confronti sono stati fatti, altrimenti richiamo la funzione min(a, size2), size2 che vale size-1, quindi quando la richiamo dovrei ripetere la funzione e avere size2 = size2-1 = size -1 -1, quindi size-2 e passare al penultimo elemento dell'array, e ripeto il confronto vedendo se poi è verificata la condizione size2==1, così fino ad analizzare tutti gli elementi dell'array... Cosa c'è di sbagliato?

[ireon]

Ragazzi, sto diventando matto, il valore di ritorno della funzione, ovverto return minimo, è sempre -1, anche se cambio gli array... Se qualcuno può aiutarmi glie ne sarei veramente molto grato...

[ireon]

[Ippo343]

Fai una funzione così:

1) se l'array ha un solo elemento, il minimo dell'array è quell'elemento.
2) se l'array ha più di un elemento, il minimo è il minore tra v[0] e il minimo del resto dell'array.

//pseudocodice

if size == 1 return v[0];

minimo = min(v[1], size-1);
return ((v[0] < min) ? v[0] : min);

[ireon]

Io alla fine l'ho implementata così:

int min (int a[], int size)

{

    int minimo;
    if (size == 1) return a[0];
    int size2 = size-1;
    if (size2<1) return minimo;
    if (a[size2] < a[0])
    {a[0]=a[size2];
    minimo = a[0];}
    else minimo = a[0];
    
    min (a, size2);

    return a[0];



}

L'ho testata e funziona, quindi penso dovrebbe andare bene...

[YuYevon]

Ci sono alcune cose inutili come

if (size2<1) return minimo;

size2 non raggiungerà mai valori minori di 1 in quella funzione, tra l'altro "minimo" non è inizializzata ad alcun valore in quel punto del codice.

Così dovrebbe andare senza istruzioni superflue

int min(int *array, int n)
{
    int min_val;

    if (n == 1) {
        return *array;
    }

    return (min_val = min(array, n - 1)) < array[n - 1] ? min_val : array[n - 1];
}

[ireon]

Ok