αναδρομή στην C

[maniac89]

ρε παιδιά ξέρετε καμιά σελίδα(ξένη ή ελληνική no problem) από την οποία θα μπορώ να μάθω να λύνω προβλήματα με αναδρομή...αν έχει και προβλήματα με λύση κιόλας καλό θα ήταν...

προκαταβολικά ευχαριστώ!

[alex2005]

Το καλύτερο κατά την γνώμη μου είναι να κάτσεις να λύσεις μερικά προβλήματα μόνος σου γιατί αλλιώς δεν θα μάθεις.

 

Αν θέλεις παραδείγματα απλά πάτα στο google "recursion examples"

 

Το πρώτο αποτέλεσμα είναι αυτό:

 

http://www.sparknotes.com/cs/recursion/examples/

[nav]

Καλησπερα παιδια !Θα ηθελα να μου λυσετε μια απορια στην αναδρομη.

Εχουμε την παρακατω συναρτηση ...

>
f(int x,int *a,int *{

 if(x>0){
     f(x-1,a,;
   (εντολες)
  }
 if(x>0){
    f(x-1,b,a);
   }
}

Στην αναδρομη ολες οι εντολες αποθηκευονται στη μνημη και εκτελουνται στο τελος με αντιστροφη σειρα.Εδω εχουμε 2 συνθηκες οπου καλειται η συναρτηση.Στη μνημη θα αποθηκευτουν μονο οι (εντολες) ή ολο το τμημα

>
(εντολες)
  }
if(x>0){
    f(x-1,b,a);
   }

ωστε να εκτελεστουν μετα ?

[defacer]

Πρώτον, οι εντολές δεν "αποθηκεύονται στη μνήμη". Δεν ξέρω ποιό ακριβώς είναι το νοητικό μοντέλο που έχεις για την εκτέλεση ενός προγράμματος, αλλά είναι τουλάχιστον σε κάποιο βαθμό λάθος.

 

Δεύτερον, δεν είναι καθόλου δεδομένο ότι αυτό που γίνεται (το λέω έτσι για να μην παραστρατήσουμε) γίνεται με αντίστροφη σειρά. Εσύ γράφεις το πρόγραμμα, γίνεται όπως του πεις να γίνει. Μπορεί σε κάποια συγκεκριμένα παραδείγματα κάτι να γίνεται με "αντίστροφη" ας πούμε σειρά (που είναι ύποπτο έτσι κι αλλιώς γιατί υπονοεί ότι υπάρχει κάποια "κανονική" σειρά) αλλά αυτό δεν είναι κανόνας.

 

Πιο σωστό και απλό είναι να πεις ότι η αναδρομική συνάρτηση f καλεί τον εαυτό της. Απο κει και πέρα, ο κώδικας που δείχνεις λέει:

 

Κλήση της f(x)

=> Κλήση της f(x-1)

=> Κάνε πράγματα με το x

=> Κλήση της f(x-1)

 

Εφόσον η συνάρτηση είναι αναδρομική, μπορείς να αντικαταστήσεις το "κλήση της f(x-1)" με το παρακάτω:

 

Κλήση της f(x-1)

=> Κλήση της f(x-2)

=> Κάνε πράγματα με το x-1

=> Κλήση της f(x-2)

 

Τελικά δηλαδή, και αν "ισιώσουμε" το δέντρο που πάει να δημιουργηθεί (βασικά δηλαδή αν τα βάλω όλα στοιχισμένα στον κάθετο άξονα, κάτι που δεν είναι απαραίτητο γιατί όσον αφορά την εκτέλεση του προγράμματος μας ενδιαφέρει μόνο η "χρονική" σειρά εκτέλεσης = από πάνω προς τα κάτω, ενώ τη στοίχιση δεξιά/αριστερά τη χρησιμοποιούμε μόνο για να ομαδοποιούμε τα πράγματα και να εξηγούμαστε καλύτερα) θα έχεις:

 

Κλήση της f(x)

=> Κλήση της f(x-2)

=> Κάνε πράγματα με το x-1

=> Κλήση της f(x-2)

=> Κάνε πράγματα με το x

=> Κλήση της f(x-2)

=> Κάνε πράγματα με το x-1

=> Κλήση της f(x-2)

 

Οπότε τώρα μπορείς να αντικαταστήσεις την "κλήση της f(x-2)" κλπ κλπ.

 

Ελπίζω να βοήθησα.

[migf1]

Καλησπερα παιδια !Θα ηθελα να μου λυσετε μια απορια στην αναδρομη.

Εχουμε την παρακατω συναρτηση ...

>
f(int x,int *a,int *{

 if(x>0){
     f(x-1,a,;
   (εντολες)
  }
 if(x>0){
	f(x-1,b,a);
   }
}

Στην αναδρομη ολες οι εντολες αποθηκευονται στη μνημη και εκτελουνται στο τελος με αντιστροφη σειρα.Εδω εχουμε 2 συνθηκες οπου καλειται η συναρτηση.Στη μνημη θα αποθηκευτουν μονο οι (εντολες) ή ολο το τμημα

>
(εντολες)
  }
if(x>0){
	f(x-1,b,a);
   }

ωστε να εκτελεστουν μετα ?

 

Βασικά η σειρά εκτέλεσης εξαρτάται α) από τη συνθήκη του base-case σε συνδυασμό με τα ορίσματα της συνάρτησης και β) από το αν οι εντολές υπολογισμού έπονται ή προηγούνται της εσωτερικής αναδρομής.

 

Στο απλό παράδειγμα που ακολουθεί οι αριθμοί φαίνεται να τυπώνονται αντίστροφα (10 9 8 7 6 5 4 3 2 1) αλλά στην ουσία τυπώνονται με τη σειρά λόγω του συνδυασμού όρισμα & base case.

 

Δηλαδή ξεκινάνε από ntimes = 10 και μειώνονται διαδοχικά επειδή στη main καλέσαμε την count με όρισμα το 10 και μέσα στην count α) το base-case ελέγχει για μηδενισμό του ορίσματος και β) η αναδρομική κλήση αφενός έπεται της εντολής printf και αφετέρου πραγματοποιείται με μειούμενο όρισμα, κατά 1 μονάδα ανά κλήση.

 

>
/* με κλήση count( 10 ) στην main θα τυπώσει: 10 9 8 7 6 5 4 3 2 1 */
void count( int ntimes )
{
if ( ntimes == 0 )	/* base case */
	return;

printf("%d ", ntimes);
count( ntimes-1 );
}
/* -------------------------------------------------------------------- */
int main( void )
{
count( 10 );
putchar('\n');

return 0;
}

 

Αν τώρα μέσα στην count μετακινήσουμε την αναδρομική κλήση πάνω από την printf, τότε βάση του ορίσματος ntimes (που εξακολουθεί να ξεκινάει από το 10) οι αριθμοί θα τυπωθούν με αντίστροφη σειρά...

 

>
/* με κλήση count( 10 ) στην main θα τυπώσει: 1 2 3 4 5 6 7 8 9 10 */
void count( int ntimes )
{
if ( ntimes == 0 )	/* base case */
	return;

count( ntimes-1 );
	printf("%d ", ntimes);
}

 

Τώρα, σε ότι αφορά το που αποθηκεύονται τα ενδιάμεσα στάδια, προφανώς αποθηκεύονται στη μνήμη αλλά όχι με τη μορφή που ενδεχομένως νομίζεις. Ανάλογα το είδος της αναδρομής (tail recursion ή όχι) και ανάλογα τη γλώσσα ή/και τον compiler δημιουργούνται ένα ή περισσότερα stack-frames για την αναδρομική συνάρτηση. Αυτά όμως ξεφεύγουν του παρόντος context, αλλά μπορείς να διαβάσεις τα σχετικά άρθρα της Wikipedia (πιστεύω είναι επαρκώς κατατοπιστικά).

 

EDIT: Συντακτικό.

[Timonkaipumpa]

Καλησπερα παιδια !Θα ηθελα να μου λυσετε μια απορια στην αναδρομη.

Εχουμε την παρακατω συναρτηση ...

>
f(int x,int *a,int *{

 if(x>0){
     f(x-1,a,;
   (εντολες)
  }
 if(x>0){
    f(x-1,b,a);
   }
}

Στην αναδρομη ολες οι εντολες αποθηκευονται στη μνημη και εκτελουνται στο τελος με αντιστροφη σειρα.Εδω εχουμε 2 συνθηκες οπου καλειται η συναρτηση.Στη μνημη θα αποθηκευτουν μονο οι (εντολες) ή ολο το τμημα

>
(εντολες)
  }
if(x>0){
    f(x-1,b,a);
   }

ωστε να εκτελεστουν μετα ?

 

 

Στην μνήμη θα "αποθηκευτούν" οι μεταβλητές.

 

Φαντάσου κάθε μία φορά που καλείς την f σαν να καλείς μία συνάρτηση μέσα στην main.

 

Το πρόγραμμα θα καλέσει την f, θα εκτελέσει την f και μετά θα επιστρέψει πάλι στην main για να συνεχίσει από εκεί που έμεινε.

 

Το ίδιο γίνεται παντού και πάντα... απλά στην αναδρομή αντί για main έχεις την f η οποία καλεί τον εαυτό της. Έτσι, όπως όταν στην main βγει από την f και θα πρέπει να συνεχίσει την main, έτσι και στην περίπτωση της αναδρομής όταν βγει από την f θα πρέπει να συνεχίσει όσο από την "άλλη" f έχει μείνει. Το αυτό μέχρι να τελειώσουν όλες οι f που έχουν κληθεί.

[Nessie]

Έχω βρει την εξής συνάρτηση. Είναι κλασικό παράδειγμα αναδρομής, οι Πύργοι του Ανόι. Μόνο που κ εγώ δεν το έχω καταλάβει απόλυτα. Αν μπορεί κάποιος να μου το εξηγήσει θα με βοηθήσει πολύ.

 

>void towers(int n,char frompeg,char topeg,char auxpeg)
{ /* If only 1 disk, make the move and return */
  if(n==1)
    { printf("\nMove disk 1 from peg %c to peg %c",frompeg,topeg);
      return;
    }
  /* Move top n-1 disks from A to B, using C as auxiliary */
  towers(n-1,frompeg,auxpeg,topeg);
  /* Move remaining disks from A to C */
  printf("\nMove disk %d from peg %c to peg %c",n,frompeg,topeg);
  /* Move n-1 disks from B to C using A as auxiliary */
  towers(n-1,auxpeg,topeg,frompeg);
}

[Timonkaipumpa]

Κάνε μόνος σου, με το χέρι, τι ακριβώς θα γίνει εάν δώσεις n = 3 και pegs A, B και C. Θα το καταλάβεις..

[Fawkes]

Έχω βρει την εξής συνάρτηση. Είναι κλασικό παράδειγμα αναδρομής, οι Πύργοι του Ανόι. Μόνο που κ εγώ δεν το έχω καταλάβει απόλυτα. Αν μπορεί κάποιος να μου το εξηγήσει θα με βοηθήσει πολύ.

 

>void towers(int n,char frompeg,char topeg,char auxpeg)
{ /* If only 1 disk, make the move and return */
  if(n==1)
    { printf("\nMove disk 1 from peg %c to peg %c",frompeg,topeg);
      return;
    }
  /* Move top n-1 disks from A to B, using C as auxiliary */
  towers(n-1,frompeg,auxpeg,topeg);
  /* Move remaining disks from A to C */
  printf("\nMove disk %d from peg %c to peg %c",n,frompeg,topeg);
  /* Move n-1 disks from B to C using A as auxiliary */
  towers(n-1,auxpeg,topeg,frompeg);
}

η λογική υπάρχει σε σχόλια στο ποστ που παρέθεσες. Όπως είπε και ο timonkaipumpa εκτέλεσε με το χέρι τη συνάρτηση. Σκέψου ότι η συνάρτηση καλεί συνέχεια τον εαυτό της και επαναλαμβάνει τις ίδιες κινήσεις...

Σόρρυ για το οφτοπικ αλλά πρέπει να ρωτήσω

nessie μήπως τυχαίνει να είσαι στο τμήμα πληροφορικής ΑΠΘ?

[Nessie]

η λογική υπάρχει σε σχόλια στο ποστ που παρέθεσες. Όπως είπε και ο timonkaipumpa εκτέλεσε με το χέρι τη συνάρτηση. Σκέψου ότι η συνάρτηση καλεί συνέχεια τον εαυτό της και επαναλαμβάνει τις ίδιες κινήσεις...

Σόρρυ για το οφτοπικ αλλά πρέπει να ρωτήσω

nessie μήπως τυχαίνει να είσαι στο τμήμα πληροφορικής ΑΠΘ?

 

Απλά δεν έχω καταλάβει καλά πως λειτουργεί η αναδρομή. Εκεί που ξανακαλεί η συνάρτηση τον εαυτό της το χάνω λίγο. Όχι, είμαι στο CSD στο Ηράκλειο.

[migf1]

Παραπάνω έχω δώσει ένα link σε σχετικό άρθρο της Wikipedia που είναι πιστεύω αρκούντως επεξηγηματικό (με την προϋπόθεση πως καταλαβαίνεις Αγγλικά). Το καλύτερο πάντως είναι να βάλεις μικρές τιμές στα ορίσματα και να το κάνεις trace με μολύβι και χαρτί. Πιθανώς με σχήματα όπως αυτό εδώ: http://en.wikipedia....er_of_execution

[V.I.Smirnov]

Στην παρακάτω επισύναψη εικονίζεται η κλήση της αναδρομικής συνάρτησης για πύργο με τρεις δίσκους.

 

Απορώ ειλικρινώς με κάποιους.

Όντας φοιτητές, το πρώτο μέρος που πρέπει να ψάχνουν για μελέτη είναι η βιβλιογραφία και η βιβλιοθήκη,

όχι forums όπως εδώ όπου γράφει ο κάθε σχετικός ή άσχετος όπως και ότι του καπνίσει.

Το συγκεκριμένο πρόβλημα είναι από τα κλασσικά και μελετάται λεπτομερώς στα περισσότερα βιβλία δομών δεδομένων.

Το διάγραμμα που παραθέτω είναι από ένα τέτοιο βιβλίο που υπάρχει στις περισσσότερες βιβλιοθήκες και

εξετάζει το πρόβλημα ενδελεχώς, βήμα βήμα. Η ανάλυση (και όλη η μελέτη της αναδρομής) είναι εξαιρετικά διδακτική

και σαφής. Θα μπορούσα να παραθέσω όλες τις σελίδες αλλά δεν θα το κάνω. Ας πάνε να το ψάξουν όπως εγώ κάποτε...

 

-