[C] funzione ricorsiva che restituisce la posizione di un elemento in una lista

[the-bit]

Buona sera,
ho questa funzione scritta in pseudocodice che restituisce la posizione della prima occorrenza di un elemento in una lista:

fonction firstPosition(x, L) // ricorsiva
{
    if isEmpty(L) true
        return 0
    else
        if x == First(L)
            return 1
        else
            y <- firstPosition(x,next(L))
        if y == 0
            return 0
        else
            return 1+y
}

le seguenti funzioni fanno quanto segue:

isEmpty // boolean
first(L) restituisce il primo elemento della lista
next(L) // resituisce una nuova lista privata del suo primo elemento

Secondo me questa funzione, non funziona perchè nell'ultimo else non vengono fatti ulteriori confronti per vedere se x==y.
Voi cosa ne pensate?

[Ippo343]

Che senso avrebbe controllare se x == y?

[the-bit]

Per questo ho aperto questo thread, perchè non ho capito come fa a funzionare questa funzione.
Potresti spiegarmelo?

[ybla82]

Ciao,
mi sembra che il metodo funzioni correttamente, senza necessità di fare confronti finali.

Il funzionamento è questo:

- la funzione verifica se il primo elemento della lista è quello cercato.
- Se si ,restituisce la posizione, altrimenti tolglie il primo elemento dalla lista e chiama se stessa.

- Chiamando se stessa, viene fatta la stessa cosa, per cui viene verificato di nuovo se il primo elemento della lista è uguale a quello cercato ( in questo caso stiamo confrontando il secondo elemento della lista originale).

- Questo passaggio viene ripetuto fino a quando non è valida la condizione x == Fist(L). In questo caso si restituisce 1.

- Il valore restituito entrerà in "else y +1". Questo passaggio verrà eseguito tante volte quante sono le chiamate ricorsive effettuate. In questo modo otterrai la posizione dell'elemento cercato.



Ti faccio un esempio pratico.

Immagina una lista di 4 elementi (A,B,C,D) e immagina di cercare C.


Prima chiamata:
- Confronti A con D-> non sono uguali.
- Togli il primo elemento dalla lista -> (B,C,D)
- Chiami la funzione "firstPosition" (Prima chiamata ricorsiva)
- Confronti B con D-> non sono uguali.
- Togli il primo elemento dalla lisya -> (C,D)
- Chiami "firstPosition". (Seconda chiamata ricorsiva)
- Confronti C con C -> sono uguali
- Ritorni 1.
- Il valore ritornato entra in "else y+1" -> ritorni quindi 2. (sei nella prima chiamata ricorsiva)
- Il valore ritornato entra in "else y+1" -> ritorni quindi 3. (sei nella prima chiamata)

La posizione di C è quindi la 3.

Spero sia comprensibile.

[the-bit]

Originariamente inviato da ybla82
....
- la funzione verifica se il primo elemento della lista è quello cercato.
- Se si ,restituisce la posizione, altrimenti tolglie il primo elemento dalla lista e chiama se stessa.

- Chiamando se stessa, viene fatta la stessa cosa, per cui viene verificato di nuovo se il primo elemento della lista è uguale a quello cercato ( in questo caso stiamo confrontando il secondo elemento della lista originale).

- Questo passaggio viene ripetuto fino a quando non è valida la condizione x == Fist(L). In questo caso si restituisce 1.

- Il valore restituito entrerà in "else y +1". Questo passaggio verrà eseguito tante volte quante sono le chiamate ricorsive effettuate. In questo modo otterrai la posizione dell'elemento cercato.

.....

E' proprio la parte in grassetto che non ho capito.
Supponendo una lista {1-2-3-4-5}, in cui voglio cercare 3 ad esempio:
prendo il primo elemento della lista, lo confronto con 3 non è uguale. quindi tolgo il primo elemento della lista e passo al successivo (che è 2); di nuovo, 2 != 3 quindi scarto anche 2.
Quando però arrivo a 3=3 mi trovo nella condizione di x==First(L), quindi ho un return 1.
Bene, quel return 1 non mi fa finire l'esecuzione del programma resituendomi 1?
E' questo passaggio che non mi è chiaro.

[ybla82]

no, perchè tu ritorni 1 dalla terza chiamata della funzione.
Poi entri nella seconda chiamata della funzione e quindi farai y+ 1 ( 1 +1 = 2) che a sua volta tornerà nella chiamata originale della funzione e ritornerà il valore finale y + 1 ( 2 +1 = 3) : il valore cercato sta nella terza posizione.


Una funzione ricorsiva vuol dire che chiama se stessa, ma non la sua stessa esecuzione, bensì un'altra.

Nello stack delle chiamate saranno due chiamate differenti.