FUNZIONE RICORSIVA_non ho capito come ragiona il C!

di il
2 risposte

FUNZIONE RICORSIVA_non ho capito come ragiona il C!

Salve, sto provando a studiare una funzione ricorsiva inserita in un codice che mi è stato fornito.
Il codice è:

// TROVARE IL VALORE MINIMO IN UN ARRAY
// Scrivete una funzione ricorsiva		recursiveMinimum		che riceva come argomenti un array intero e la dimensione dell'array
// e restituisca l'elemento più piccolo dell'array. La funzione deve arrestare l'elaborazione e tornare alla funzione chiamante
// quando riceve un array di un solo elemento.

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define SIZE 10
#define MAXRANGE 1000

// prototipo di funzione
int recursiveMinimum( int array[], unsigned int lowIndex, unsigned int highIndex);

int main(void){
	srand(time(NULL));
	int array[SIZE]; // array dove eseguire la ricerca
	
	// inizializza gli elementi dell'array a numeri casuali
	for( unsigned int loop = 0; loop < SIZE; ++loop) {
		array[loop] = 1 + rand() % MAXRANGE;
	}
	printf( "Array memebers are: \n" );

	// stampa l'array
	for( unsigned int loop = 0; loop < SIZE; ++loop ) {
		printf( " %d ", array[loop] );
	}
	
	// trova e stampa l'elemento più piccolo dell'array 
	puts( "" );
	int smallest = recursiveMinimum( array, 0, SIZE - 1 );
	printf( "\nSmallest element is: %d\n", smallest );
}

// funzione per trovare ricorsivamente l'elemento minimo dell'array
int recursiveMinimum( int array[], unsigned int lowIndex, unsigned int highIndex ) {
	// se l'array ha un solo elemento il valore di quell' elemento è il valore più piccolo dell'array
	if( lowIndex == highIndex ) {
		return array[highIndex];
	} else {
		int min = recursiveMinimum(array, lowIndex + 1, highIndex);

		printf( "min is: %d\tarray lowIndex is: %d\n", min, array[lowIndex] );

		return array[lowIndex] < min ? array[lowIndex] : min;
	}
}
L'output è questo:

Array memebers are:
905 88 928 592 392 513 478 396 444 311
min is: 311 array lowIndex is: 444
min is: 311 array lowIndex is: 396
min is: 311 array lowIndex is: 478
min is: 311 array lowIndex is: 513
min is: 311 array lowIndex is: 392
min is: 311 array lowIndex is: 592
min is: 311 array lowIndex is: 928
min is: 311 array lowIndex is: 88
min is: 88 array lowIndex is: 905
Smallest element is: 88


La funzione ricorsiva è:

// funzione per trovare ricorsivamente l'elemento minimo dell'array
int recursiveMinimum( int array[], unsigned int lowIndex, unsigned int highIndex ) {
	// se l'array ha un solo elemento il valore di quell' elemento è il valore più piccolo dell'array
	if( lowIndex == highIndex ) {
		return array[highIndex];
	} else {
		int min = recursiveMinimum(array, lowIndex + 1, highIndex);

		printf( "min is: %d\tarray lowIndex is: %d\n", min, array[lowIndex] );

		return array[lowIndex] < min ? array[lowIndex] : min;
	}
}
Non riesco a capire come ragiona la funzione ricorsiva. Ho capito che, se dal programma passo come argomenti alla funzione ricorsiva array, 0 e SIZE -1, nel corso della funzione ricorsiva, si salta sempre il passaggio
if( lowIndex == highIndex )
fin quando non sarà chiamata la funzione ricorsiva
int min = recursiveMinimum(array, 9, 9);
. Ora avremo lowIndex == highIndex che ci darà come valore di "min" min = array[highIndex]. Quindi la funzione continuerà la sua esecuzione, verrà stampato a schermo il valore "min" ed il valore temporaneo di "array[lowIndex]" e poi avremo il return, in questo caso "min". A questo punto la funzione dovrebbe ritornare al programma e darmi int smallest = recursiveMinimum( array, 0, SIZE - 1 ); cioè smallest = 311 ma il problema è che non capisco come fa ad arrivare al giusto valore minimo non essendoci un ciclo for, per esempio, che scali il valore temporaneo di array[lowIndex].

Non so se sono stato chiaro ma credo che potrei spiegarmi meglio se non avete capito.
Grazie!

2 Risposte

  • Re: FUNZIONE RICORSIVA_non ho capito come ragiona il C!

    Incredibile come la funzione ricorsiva metta in crisi tutti quanti senza motivo.

    La logica è esattamente identica a quella di tutte le chiamate ad altre funzioni. Fai finta che venga chiamata recursiveMinimum_1, recursiveMinimum_2 eccetera, come se fossero funzioni differenti. Appena una delle funzioni arriva al return, riprende l'esecuzione della funzione che l'ha chiamata dalla riga successiva
  • Re: FUNZIONE RICORSIVA_non ho capito come ragiona il C!

    Il fatto è, secondo me, che il concetto di stack (e il suo utilizzo da parte delle funzioni) viene affrontato pochissimo (e male) durante lo studio. E invece la sua perfetta comprensione è alla base di questi argomenti a prima vista ostici.
Devi accedere o registrarti per scrivere nel forum
2 risposte