False ricorsione vs vera ricorsione [chiuso]

Question

False ricorsione vs vera ricorsione [chiuso]

#1 da (5 voti)

0

Sono stato avvertito dal mio professore di evitare la "falsa ricorsione", in cui una funzione si comporta in modo ricorsivo, ma non ha un lavoro ricorsivo utile. Credo di capire la ricorsione, ma vorrei ricontrollare.

Ho scritto un breve programma di ordinamento ricorsivo che ordina (ricorsivamente spero) l'array dato, ignorando il primo elemento. Dopo aver ordinato tutti gli elementi dopo il primo, posiziona il primo elemento nella posizione corretta all'interno della matrice secondaria ordinata (spostando gli elementi a sinistra).

Il codice è il seguente:

#include <iostream> // for cout
using namespace std;

void RecSort(int*, int, int); //RecSort function declaration
int arr[8] = {4,1,2,7,5,9,0,2}; //global array to sort (just an example)

void RecSort(int* arr, int len, int curr)       { //RecSort definition
        if (curr < len - 2)     { //-1 to agrre with 0 indexing, -1 to stop 1 element before the end (terminating condition)
                RecSort(arr, len, curr + 1); //recursively sort all elements except first element
        }
        for (int i = curr; i < len - 2; i++)    { // once the rest of the array is sorted, shift elements to the left of the first element
                if (arr[i] > arr[i + 1])        { // while appropriate (in this case, sort ascending order)
                        int temp = arr[i + 1]; //swap array elements if needed
                        arr[i + 1] = arr[i];
                        arr[i] = temp;
                }
        }
}

int main()      {

int length, current;
RecSort(arr, length = 8, current = 0);// sort array (recursively?)
        for (int i = 0; i < length - 1; i++)    {
                cout << arr[i] << " "; //print array to verify functionality
        }
}

Questo sembra essere veramente ricorsivo?

recursion

posta user207045 09.12.2015 - 19:54

fonte

1 risposta

Leggi altre domande sui tag recursion

Sarebbe possibile creare architetture funzionali, orientate agli oggetti o dichiarative? [chiuso] Come strutturare un'applicazione SaaS?

score 5 · Accepted Answer

Non ho mai visto prima il termine "falsa ricorsione" e sembra che potrebbe essere la terminologia originale del tuo professore. Di conseguenza, è un po 'difficile giudicare ciò che ritiene sia qualificato. Immagino che voglia dire che la funzione può essere facilmente riscritta usando un ciclo invece di ricorsione, quindi non ha bisogno di essere ricorsivo.

Come regola generale, se una funzione deve essere ricorsiva, chiamerà se stessa più volte. Quando una funzione si chiama solo una volta, di solito può essere riscritta come un loop.

Nel tuo caso, ciò che stai facendo è ordinare l'ultimo elemento, quindi gli ultimi due elementi, quindi gli ultimi tre elementi, ecc. Puoi implementarlo come un ciclo simile a:

for (int startIndex = length - 1, startIndex >= 0; startIndex++) {
    // do what you would have done before.

Quello che hai fatto qui è implementato un ordinamento per inserzione, il suo non tipicamente implementato in modo ricorsivo.