Αναδρομή σε C

[orionas]

Καλημέρα, 

μπορεί κάποιος να μου εξηγήσει πως λειτουργεί η παρακάτω αναδρομή;

 

Τι επιστρέφει η κλήση foo(5);

int foo(int n) {

if (n<=1)

return 1;

return foo(n-1) + foo(n-2);

}

 

Ευχαριστώ.

[imitheos]

Καλημέρα, 

μπορεί κάποιος να μου εξηγήσει πως λειτουργεί η παρακάτω αναδρομή;

 

Τι επιστρέφει η κλήση foo(5);

int foo(int n) {

if (n<=1)

return 1;

return foo(n-1) + foo(n-2);

}

 

Ευχαριστώ.

   Αν Ν μικρότερο ή ίσο του 1
      τότε επίστρεψε 1
   αλλιώς κάλεσε την συνάρτηση για ν-1, για ν-2 και επίστρεψε το άθροισμα τους

Είτε με τον C κώδικα είτε με τον αντίστοιχο ψευδοκώδικα, γιατί δεν τρέχεις χειροκίνητα την συνάρτηση για ν = 5 και να μας πεις τι κάνει ?

[gon1332]

Αρχικά.

 

Καλείς τη συνάρτηση με 5.

Ελέγχεται η τιμή του n: Αυτή είναι η συνθήκη τερματισμού της αναδρομής.

Τέλος, αν δεν ισχύει καλείται η ίδια η συνάρτηση 2 φορές και ό,τι τιμές επιστρέψουν, αυτές προστίθενται κι επιστρέφονται.

 

Αυτό γίνεται κάθε φορά, μέχρι όλες οι κλήσεις στη foo να μπουν στη συνθήκη τερματισμού. Προσπάθησε

μία να το τρέξεις με τη βοήθεια ενός δενδρικού σχήματος κι αν αντιμετωπίσεις δυσκολία πες μας.

[AllCowsEatGrass]

foo(5)           =>

foo(4) + foo(3)  =>

...

[orionas]

Ευχαριστώ όλους σας για την βοήθεια, απλά δε μπορώ να καταλάβω γιατί επιστρέφει 8.Πως λειτουργεί "εσωτερικά"  η αναδρομή;Τι επιστρέφουν κάθε φορά οι foo;

[imitheos]

Πως λειτουργεί "εσωτερικά"  η αναδρομή;Τι επιστρέφουν κάθε φορά οι foo;

Ίσως να μην το εξηγήσαμε αρκετά κατανοητά αλλά τα μηνύματα και των τριών μας αυτό που ρωτάς εξηγούν.

[gon1332]

Για κάλεσε τη foo με 1 και βγάλε το αποτέλεσμα στο χαρτί. Ελπίζω να γίνουν όλα προφανή.

 

Η αναδρομή συμβαίνει απλά, όταν σε μία συνάρτηση, υπάρχει τουλάχιστον μία κλήση στη

ίδια τη συνάρτηση. Βλέπε foo.

 

Επίσης δες αυτές τις δύο διαλέξεις απ'το αντίστοιχο μάθημα της σχολή του Βόλου. [1], [2]

(στο link των διαλέξεων θα βρεις και παραδείγματα δίπλα από κάποια θέματα)

[AllCowsEatGrass]

Προσπάθησε να συνεχίσεις στο χαρτί (ανέφερε και ο Gon το χαρτί, δεν είναι τυχαίο) αυτό που σου έγραψα. Σε κάποια φάση θα φτάσεις σε foo(1) ή foo(0). Τι θα γίνει στην επόμενη γραμμη;

[orionas]

Ευχαριστώ πολύ παιδιά,Θα το κοιτάξω σήμερα.Πιστεύω να το καταλάβω.Να είστε καλά.

[albNik]

Δεστο μαθηματικά 

f(x)=f(x-1)+f(x-2) για x>1

f(x)=1 για x<=1

 

f(5)=f(4)+f(3)=[f(3)+f(2)] + [f(2)+f(1)]

=[f(2)+f(1)+f(1)+f(0)] + [f(1)+f(0)+1]

= [f(1)+f(0)+1+1+1] + [1+1+1]=5+3=8

[orionas]

συγνώμη για την ταλαιπωρία αλλά για n=1 έτρεχα την foo(n-1) + foo(n-2).Ζέστη και κούραση (ή βλακεία με χάζεψαν.Σας ευχαριστώ πάντως εκ βάθους καρδίας.Ιδιαίτερα για τα λίνκς.