FUNZIONE RICORSIVA_non ho capito come ragiona il C!

di Anonimizzato21577 il
2 risposte
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

  • 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
  • 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