Τι είναι η αναδρομή και πότε πρέπει να το χρησιμοποιώ;

ψήφοι
121

Ένα από τα θέματα που φαίνεται να έρχονται τακτικά στις λίστες και online συζητήσεις είναι τα πλεονεκτήματα (ή την έλλειψη αυτών) να κάνει μια Computer Science Degree. Ένα επιχείρημα που φαίνεται να έρχονται ξανά και ξανά για το αρνητικό μέρος είναι ότι έχουν κωδικοποίησης για κάποιο αριθμό ετών και δεν έχουν χρησιμοποιήσει ποτέ αναδρομή.

Το ερώτημα λοιπόν είναι:

  1. Τι είναι η αναδρομή;
  2. Πότε θα μπορώ να χρησιμοποιήσω αναδρομή;
  3. Γιατί οι άνθρωποι δεν χρησιμοποιούν αναδρομή;
Δημοσιεύθηκε 06/08/2008 στις 03:29
πηγή χρήστη
Σε άλλες γλώσσες...                            


40 απαντήσεις

ψήφοι
86

Υπάρχουν αρκετές καλές εξηγήσεις αναδρομή σε αυτό το νήμα, η απάντηση είναι σχετικά με το γιατί δεν πρέπει να το χρησιμοποιήσετε στις περισσότερες γλώσσες. * Στην πλειονότητα των μεγάλων επιτακτική ανάγκη γλώσσα εφαρμογές (δηλαδή κάθε σημαντική εφαρμογή της C, C ++, Basic, Python , Ruby, Java και C #) επανάληψη είναι κατά πολύ προτιμότερη από την αναδρομή.

Για να καταλάβει κανείς γιατί, με τα πόδια μέσα από τα βήματα που οι παραπάνω γλώσσες χρησιμοποιούν για να καλέσετε μια συνάρτηση:

  1. ο χώρος είναι σκαλισμένα σε στοίβα για τα επιχειρήματα της λειτουργίας και τοπικές μεταβλητές
  2. Τα επιχειρήματα της συνάρτησης αντιγράφονται σε αυτό το νέο χώρο
  3. ελέγχου άλματα στη λειτουργία
  4. τρέχει κώδικα της συνάρτησης
  5. αποτέλεσμα της συνάρτησης αντιγράφεται σε μια τιμή επιστροφής
  6. η στοίβα τυλίγεται στην προηγούμενη θέση του
  7. ελέγχου άλματα πίσω στο σημείο όπου κλήθηκε η συνάρτηση

Να κάνει όλα αυτά τα βήματα απαιτεί χρόνο, συνήθως λίγο περισσότερο από ό, τι χρειάζεται για να επαναλάβει μέσω ενός βρόχου. Ωστόσο, το πραγματικό πρόβλημα είναι το βήμα # 1. Όταν πολλά προγράμματα ξεκινήσει, θα διαθέσει ένα ενιαίο κομμάτι της μνήμης για τη στοίβα τους, και όταν εξαντληθεί της μνήμης (συχνά, αλλά όχι πάντα λόγω αναδρομή), το πρόγραμμα διακόπτεται οφείλεται σε υπερχείλιση στοίβας .

Έτσι, σε αυτές τις γλώσσες αναδρομή είναι πιο αργή και καθιστά ευάλωτο σε συντριβή. Υπάρχουν ακόμα μερικά επιχειρήματα για τη χρήση του όμως. Σε γενικές γραμμές, κώδικα που γράφεται αναδρομικά είναι μικρότερη και λίγο πιο κομψό, μόλις ξέρετε πώς να το διαβάσετε.

Υπάρχει μια τεχνική που γλώσσας υλοποιητές μπορούν να χρησιμοποιήσουν ονομάζεται βελτιστοποίηση κλήσης ουράς η οποία μπορεί να εξαλείψει ορισμένες τάξεις της στοίβας υπερχείλισης. Λίγα λόγια: αν η έκφραση επιστροφή ενός συνάρτησης είναι απλά το αποτέλεσμα μιας κλήσης συνάρτησης, τότε δεν χρειάζεται να προσθέσετε ένα νέο επίπεδο στη στοίβα, μπορείτε να χρησιμοποιήσετε ξανά την τρέχουσα για τη λειτουργία που ονομάζεται. Δυστυχώς, λίγες επιτακτική ανάγκη γλώσσα-εφαρμογές έχουν βελτιστοποίηση ουρά-κλήση ενσωματωμένο.

* Μου αρέσει αναδρομή. Το αγαπημένο μου στατική γλώσσα δεν χρησιμοποιεί βρόχους σε όλα, αναδρομή είναι ο μόνος τρόπος για να γίνει κάτι κατ 'επανάληψη. Απλά δεν νομίζω ότι η αναδρομή είναι γενικά μια καλή ιδέα σε γλώσσες που δεν είναι συντονισμένοι για αυτό.

** Με την ευκαιρία Mario, το τυπικό όνομα για τη λειτουργία ArrangeString σας είναι «ενταχθούν», και θα ήμουν έκπληκτος αν η γλώσσα της επιλογής σας δεν διαθέτει ήδη μια εφαρμογή του.

Απαντήθηκε 06/08/2008 στις 06:09
πηγή χρήστη

ψήφοι
63

Απλή αγγλικά παράδειγμα της αναδρομής.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.
Απαντήθηκε 04/05/2010 στις 17:38
πηγή χρήστη

ψήφοι
49

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

struct Node {
    Node* next;
};

Και θέλετε να μάθετε πόσο καιρό ένα συνδεδεμένη λίστα είναι ότι μπορείτε να το κάνετε αυτό με αναδρομή:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Αυτό θα μπορούσε φυσικά να γίνει με ένα βρόχο for επίσης, αλλά είναι χρήσιμη ως απεικόνιση της εννοίας)

Απαντήθηκε 04/05/2010 στις 12:25
πηγή χρήστη

ψήφοι
46

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

Το πιο απλό παράδειγμα είναι η αναδρομή ουρά όπου η τελευταία γραμμή της συνάρτησης είναι μια πρόσκληση για τον εαυτό της:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

Ωστόσο, αυτό είναι ένα κουτσό, σχεδόν άχρηστη παράδειγμα, επειδή μπορεί εύκολα να αντικατασταθεί από πιο επανάληψη. Μετά από όλα, αναδρομή πάσχει από εναέρια κλήση της συνάρτησης, η οποία στο παραπάνω παράδειγμα θα μπορούσε να είναι σημαντική σε σύγκριση με τη λειτουργία στο εσωτερικό της ίδιας της συνάρτησης.

Έτσι, ολόκληρος ο λόγος να κάνουμε αναδρομή παρά επανάληψη θα πρέπει να επωφεληθούν από την στοίβα κλήσεων για να κάνετε κάποια έξυπνα πράγματα. Για παράδειγμα, εάν καλέσετε μια συνάρτηση πολλές φορές με διαφορετικές παραμέτρους μέσα στο ίδιο βρόχο τότε αυτό είναι ένας τρόπος για να επιτευχθεί διακλάδωσης . Ένα κλασικό παράδειγμα είναι το Sierpinski τρίγωνο .

εισάγετε περιγραφή της εικόνας εδώ

Μπορείτε να σχεδιάσετε ένα από αυτά τα πολύ απλά με αναδρομή, όπου τα κλαδιά στοίβα κλήσεων σε 3 κατευθύνσεις:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

Αν προσπαθήσετε να κάνετε το ίδιο πράγμα με επανάληψη νομίζω ότι θα βρείτε αυτό παίρνει πολύ περισσότερο κώδικα για να επιτευχθεί.

Άλλες περιπτώσεις κοινή χρήση μπορεί να περιλαμβάνει διάσχιση ιεραρχίες, π.χ. ιστοσελίδα αντιολισθητικές αλυσίδες, οι συγκρίσεις κατάλογο, κ.λπ.

συμπέρασμα

Σε πρακτικό επίπεδο, αναδρομή κάνει το πιο λογικό κάθε φορά που θα χρειαστεί επαναληπτική διακλάδωση.

Απαντήθηκε 04/05/2010 στις 14:33
πηγή χρήστη

ψήφοι
28

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

Η κανονική παράδειγμα είναι μια ρουτίνα για να δημιουργήσει το παραγοντικό n. Το παραγοντικό n υπολογίζεται με πολλαπλασιασμό όλους τους αριθμούς μεταξύ 1 και n. Μια επαναληπτική λύση σε C # μοιάζει με αυτό:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

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

Το επαναληπτικό βρεθεί λύση αναγνωρίζοντας ότι η νιοστή Παραγοντικό είναι n * Γεγονός (n-1). Ή για να το θέσω αλλιώς, αν γνωρίζετε τι ένα συγκεκριμένο αριθμό Παραγοντική είναι ότι μπορείτε να υπολογίσετε το επόμενο. Εδώ είναι η αναδρομική λύση σε C #:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

Το πρώτο μέρος αυτής της λειτουργίας είναι γνωστή ως βασικού σεναρίου (ή μερικές φορές Φρουρά ρήτρα) και είναι αυτό που εμποδίζει τον αλγόριθμο από το τρέξιμο για πάντα. Επιστρέφει μόνο την τιμή 1 όταν η συνάρτηση καλείται με τιμή 1 ή λιγότερο. Το δεύτερο μέρος είναι πιο ενδιαφέρουσα και είναι γνωστό ως το Αναδρομική βήμα . Εδώ καλούμε την ίδια μέθοδο με μια ελαφρώς τροποποιημένη παράμετρο (θα το ελαττώσει κατά 1) και, στη συνέχεια, πολλαπλασιάστε το αποτέλεσμα με αντίγραφο μας n.

Όταν συνάντησε για πρώτη φορά αυτό μπορεί να είναι το είδος σύγχυση γι 'αυτό είναι χρήσιμο να εξετάσουμε πώς λειτουργεί όταν τρέχει. Φανταστείτε ότι καλούμε FactRec (5). Μπαίνουμε τη ρουτίνα, δεν πήρε από το βασικό σενάριο και έτσι καταλήγουμε σαν αυτό:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

Αν εισέλθει εκ νέου τη μέθοδο με την παράμετρο 4 που και πάλι δεν σταμάτησε από τη ρήτρα φρουρά και έτσι καταλήγουμε σε:

// In FactRec(4)
return 4 * FactRec(3);

Αν αντικαταστήσουμε αυτή την τιμή επιστροφής στην τιμή επιστροφής παραπάνω παίρνουμε

// In FactRec(5)
return 5 * (4 * FactRec(3));

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

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

Αυτό τελικό υποκατάστασης συμβαίνει όταν η βασική περίπτωση ενεργοποιείται. Σε αυτό το σημείο έχουμε μια απλή algrebraic φόρμουλα για να λύσει το οποίο ισοδυναμεί άμεσα με τον ορισμό των παραγοντικών στην πρώτη θέση.

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

Απαντήθηκε 06/08/2008 στις 03:54
πηγή χρήστη

ψήφοι
12

Αναδρομή είναι η επίλυση ενός προβλήματος με μια λειτουργία που αυτοαποκαλείται. Ένα καλό παράδειγμα αυτού είναι ένα παραγοντικό λειτουργία. Παραγοντικό είναι ένα μαθηματικό πρόβλημα όπου παραγοντικό 5, για παράδειγμα, είναι 5 * 4 * 3 * 2 * 1. Αυτή η λειτουργία λύνει αυτό σε C # για θετικούς ακέραιους (δεν έχουν δοκιμαστεί - μπορεί να υπάρχει ένα bug).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}
Απαντήθηκε 04/05/2010 στις 12:29
πηγή χρήστη

ψήφοι
9

Σκεφτείτε ένα παλιό, πολύ γνωστό πρόβλημα :

Στα μαθηματικά, ο μέγιστος κοινός διαιρέτης (GCD) ... των δύο ή περισσοτέρων μη μηδενική ακέραιοι, είναι ο μεγαλύτερος θετικός ακέραιος που διαιρεί τους αριθμούς χωρίς υπόλοιπο.

Ο ορισμός της gcd είναι εκπληκτικά απλή:

ορισμός gcd

όπου mod είναι ο χειριστής modulo (δηλαδή, το υπόλοιπο μετά ακέραιος διαίρεσης).

Στα αγγλικά, ο ορισμός αυτός λέει ότι το μέγιστο κοινό διαιρέτη οποιοδήποτε αριθμό και το μηδέν είναι ο αριθμός, και το μέγιστο κοινό διαιρέτη δύο αριθμών m και n είναι το μέγιστο κοινό διαιρέτη των n και το υπόλοιπο μετά τη διαίρεση m από n .

Αν θέλετε να μάθετε γιατί αυτό λειτουργεί, ανατρέξτε στο άρθρο της Wikipedia σχετικά με το αλγόριθμο Ευκλείδεια .

Ας υπολογίσουμε gcd (10, 8) ως παράδειγμα. Κάθε βήμα είναι ίσο με το ένα λίγο πριν:

  1. gcd (10, 8)
  2. gcd (10, 10 mod 8)
  3. gcd (8, 2)
  4. gcd (8, 8 mod 2)
  5. gcd (2, 0)
  6. 2

Στο πρώτο βήμα, 8 δεν είναι ίσο με το μηδέν, οπότε ισχύει το δεύτερο μέρος του ορισμού. 10 mod 8 = 2, επειδή 8 πηγαίνει σε 10 μία φορά με ένα υπόλοιπο 2. Στο βήμα 3, το δεύτερο μέρος εφαρμόζει και πάλι, αλλά αυτή τη φορά 8 mod 2 = 0, επειδή 2 διαιρεί 8 χωρίς υπόλοιπο. Στο βήμα 5, το δεύτερο όρισμα είναι 0, οπότε η απάντηση είναι 2.

Παρατηρήσατε ότι gcd εμφανίζεται τόσο τα αριστερά και δεξιά του ίσον; Ένας μαθηματικός θα έλεγε ο ορισμός αυτός είναι αναδρομικές, επειδή η έκφραση είστε καθορισμό επανέρχεται στο εσωτερικό ορισμό της.

Αναδρομικές ορισμοί έχουν την τάση να είναι κομψό. Για παράδειγμα, ένα αναδρομικό ορισμό για το σύνολο της λίστας είναι

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

όπου headείναι το πρώτο στοιχείο σε μια λίστα και tailείναι το υπόλοιπο της λίστας. Σημειώστε ότι sumεπαναλαμβάνεται στο εσωτερικό ορισμό του στο τέλος.

Ίσως θα προτιμούσατε τη μέγιστη τιμή σε μια λίστα αντ 'αυτού:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

Μπορείτε να ορίσετε τον πολλαπλασιασμό των μη-αρνητικών ακεραίων αναδρομικά να το μετατρέψει σε μια σειρά από προσθήκες:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

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

Συγχώνευση είδος έχει μία υπέροχη αναδρομικό ορισμό:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Αναδρομική ορισμοί είναι όλα γύρω, αν ξέρεις τι να αναζητήσουν. Παρατηρήστε πως όλες αυτές οι ορισμοί έχουν πολύ απλές περιπτώσεις βάσης, π.χ. , gcd (m, 0) = m. Η αναδρομική περιπτώσεις υπονόμευσης το πρόβλημα να πιάσουμε τις εύκολες απαντήσεις.

Με αυτή την κατανόηση, μπορείτε τώρα να εκτιμήσουν τους άλλους αλγόριθμους σε άρθρο της Wikipedia για αναδρομής !

Απαντήθηκε 04/05/2010 στις 14:58
πηγή χρήστη

ψήφοι
9

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

Για παράδειγμα, για να υπολογίσετε το παραγοντικό του αριθμού X, μπορεί κανείς να την εκπροσωπήσει ως X times the factorial of X-1. Έτσι, η μέθοδος «recurses» για να βρείτε το παραγοντικό του X-1, και στη συνέχεια, πολλαπλασιάζει ό, τι πήρε από το Xνα δώσει μια τελική απάντηση. Φυσικά, για να βρείτε το παραγοντικό του X-1, αυτό θα υπολογιστεί πρώτα το παραγοντικό X-2, και ούτω καθεξής. Η βασική περίπτωση θα ήταν όταν Xείναι 0 ή 1, στην οποία περίπτωση το ξέρει να επιστρέψει 1από το 0! = 1! = 1.

Απαντήθηκε 04/05/2010 στις 12:26
πηγή χρήστη

ψήφοι
9
  1. Μια λειτουργία που καλεί τον εαυτό της
  2. Όταν μια λειτουργία μπορεί να είναι (εύκολα) αποσυντίθεται σε μια απλή λειτουργία συν την ίδια λειτουργία σε κάποιο μικρότερο τμήμα του προβλήματος. Θα πρέπει να πω, μάλλον, ότι αυτό είναι ένας καλός υποψήφιος για την αναδρομή κάνει.
  3. Το κάνουν!

Η κανονική παράδειγμα είναι το παραγοντικό που μοιάζει με:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

Σε γενικές γραμμές, αναδρομή δεν είναι απαραίτητα γρήγορη (εναέρια κλήση της συνάρτησης τείνει να είναι υψηλή, λόγω αναδρομικές συναρτήσεις τείνουν να είναι μικρές, βλέπε παραπάνω) και μπορεί να υποφέρουν από κάποια προβλήματα (ο καθένας στοίβα υπερχείλιση;). Μερικοί λένε ότι έχουν την τάση να είναι δύσκολο να πάρει το «δικαίωμα» σε μη τετριμμένες περιπτώσεις, αλλά εγώ πραγματικά δεν αγοράζουν σε αυτό. Σε ορισμένες περιπτώσεις, αναδρομή κάνει το περισσότερο νόημα και είναι το πιο κομψό και σαφή τρόπο για να γράψετε μια συγκεκριμένη λειτουργία. Θα πρέπει να σημειωθεί ότι ορισμένες γλώσσες ευνοούν αναδρομικές λύσεις και να βελτιστοποιήσουν τους πολύ περισσότερο (LISP έρχεται στο μυαλό).

Απαντήθηκε 06/08/2008 στις 03:35
πηγή χρήστη

ψήφοι
7

Μια αναδρομική συνάρτηση είναι μία η οποία καλεί τον εαυτό της. Ο πιο συνηθισμένος λόγος που έχω βρεθεί να χρησιμοποιήσετε αυτή διασχίζει μια δομή δέντρου. Για παράδειγμα, αν έχω ένα TreeView με πλαίσια ελέγχου (σκεφτείτε την εγκατάσταση ενός νέου προγράμματος, «επιλέξτε χαρακτηριστικά για την εγκατάσταση» σελίδα), θα θελήσετε ένα κουμπί «check όλους», το οποίο θα ήταν κάτι σαν αυτό (ψευδοκώδικα):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

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

Θα πρέπει να είστε λίγο προσεκτικοί με αναδρομή. Αν μπει σε ένα άπειρο βρόχο αναδρομικές, θα πάρετε μια εξαίρεση Υπερχείλιση στοίβας :)

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

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

Απαντήθηκε 06/08/2008 στις 03:44
πηγή χρήστη

ψήφοι
5

Η αναδρομή είναι μια έκφραση άμεσα ή έμμεσα αναφορά η ίδια.

Σκεφτείτε αναδρομικές ακρωνύμια ως ένα απλό παράδειγμα:

  • GNU σημαίνει GNU δεν είναι Unix
  • PHP σημαίνει PHP: Hypertext Preprocessor
  • YAML σημαίνει YAML Δεν είναι Markup Language
  • WINE σημαίνει κρασί δεν είναι ένας Emulator
  • VISA σημαίνει Visa International Association Υπηρεσία

Περισσότερα παραδείγματα για την Wikipedia

Απαντήθηκε 04/05/2010 στις 12:56
πηγή χρήστη

ψήφοι
5

Εδώ είναι ένα απλό παράδειγμα: πόσα στοιχεία σε ένα σύνολο. (Υπάρχουν καλύτεροι τρόποι να μετρήσει τα πράγματα, αλλά αυτό είναι ένα ωραίο απλό αναδρομική παράδειγμα.)

Πρώτον, χρειαζόμαστε δύο κανόνες:

  1. εάν το σύνολο είναι άδειο, ο αριθμός των στοιχείων στο σύνολο είναι μηδέν (duh!).
  2. αν το σύνολο δεν είναι κενό, η μέτρηση είναι ένα συν ο αριθμός των στοιχείων στο σύνολο μετά από ένα στοιχείο έχει αφαιρεθεί.

Ας υποθέσουμε ότι έχετε μια σειρά σαν αυτό: [xxx]. ας μετρήσει πόσα είδη υπάρχουν.

  1. Το σύνολο είναι [xxx], η οποία δεν είναι άδειο, οπότε με εφαρμογή του κανόνα 2, ο αριθμός των ειδών είναι ένα συν τον αριθμό των ειδών σε [xx] (δηλαδή θα αφαιρέσει ένα αντικείμενο).
  2. Το σύνολο είναι [xx], έτσι ώστε να εφαρμόζουν τον κανόνα 2 ακόμη φορά: το νούμερο ένα + αντικειμένων στο [x].
  3. Το σύνολο είναι [x], το οποίο εξακολουθεί να ταιριάζει με τον κανόνα 2: ένα + αριθμός στοιχείων σε [].
  4. Τώρα η σειρά είναι [], η οποία ταιριάζει με τον κανόνα 1: ο αριθμός είναι μηδέν!
  5. Τώρα που γνωρίζουμε την απάντηση στο βήμα 4 (0), μπορούμε να λύσουμε το βήμα 3 (1 + 0)
  6. Επίσης, τώρα που γνωρίζουμε την απάντηση στο βήμα 3 (1), μπορούμε να λύσουμε το βήμα 2 (1 + 1)
  7. Και τέλος, τώρα που γνωρίζουμε την απάντηση στο βήμα 2 (2), μπορούμε να λύσουμε το βήμα 1 (1 + 2) και να πάρει τον αριθμό των στοιχείων στο [xxx], η οποία είναι 3. Ζήτω!

Μπορούμε να αντιπροσωπεύουν αυτό ως:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

Κατά την εφαρμογή μιας επαναληπτικής λύση, που συνήθως έχουν τουλάχιστον 2 κανόνες:

  • η βάση, η απλή υπόθεση η οποία αναφέρει τι συμβαίνει όταν έχουν «εξαντληθεί» όλα τα δεδομένα σας. Αυτό είναι συνήθως κάποια παραλλαγή του «αν είστε εκτός των δεδομένων για την επεξεργασία, η απάντησή σας είναι Χ»
  • το αναδρομικό κανόνα, το οποίο ορίζει τι θα συμβεί, αν έχετε ακόμα τα δεδομένα. Αυτό είναι συνήθως ένα είδος κανόνα που λέει ότι «κάνουμε κάτι για να κάνουν τα δεδομένα σας που μικρότερα, και εφαρμόστε ξανά τους κανόνες σας με το μικρότερο σύνολο δεδομένων.»

Αν μετατρέψουμε το παραπάνω σε ψευδοκώδικα, έχουμε:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

Υπάρχει πολύ πιο χρήσιμα παραδείγματα (που διασχίζει ένα δέντρο, για παράδειγμα), η οποία είμαι βέβαιος ότι άλλοι άνθρωποι θα καλύψει.

Απαντήθηκε 06/08/2008 στις 04:12
πηγή χρήστη

ψήφοι
5

Αναδρομή λειτουργεί καλύτερα με ό, τι μου αρέσει να αποκαλούμε «φράκταλ προβλήματα», όπου έχουμε να κάνουμε με ένα μεγάλο πράγμα που είναι κατασκευασμένα από μικρότερες εκδόσεις των εν λόγω μεγάλο πράγμα, καθένα από τα οποία είναι ακόμα μικρότερη έκδοση του μεγάλο πράγμα, και ούτω καθεξής. Αν έχετε ποτέ να διασχίσει ή να αναζητήσετε μέσα από κάτι σαν ένα δέντρο ή ένθετη ταυτόσημες δομές, έχετε ένα πρόβλημα που θα μπορούσε να είναι ένας καλός υποψήφιος για την αναδρομή.

Οι άνθρωποι αποφεύγουν αναδρομή για διάφορους λόγους:

  1. Οι περισσότεροι άνθρωποι (συμπεριλαμβανομένου και εμού) έκοψε τα δόντια του προγραμματισμού τους για διαδικαστικούς ή αντικειμενοστρεφή προγραμματισμό, σε αντίθεση με λειτουργικό προγραμματισμό. Για αυτούς τους ανθρώπους, η επαναληπτική προσέγγιση (συνήθως με τη χρήση loops) αισθάνεται πιο φυσικό.

  2. Όσοι από εμάς μειώσει τα δόντια του προγραμματισμού μας για διαδικαστικούς ή αντικειμενοστραφή προγραμματισμό έχουν συχνά είπε να αποφευχθεί η αναδρομή γιατί είναι επιρρεπής σε λάθη.

  3. Είμαστε συχνά λένε ότι αναδρομή είναι αργή. Κλήση και την επιστροφή του από την ρουτίνα επανειλημμένα περιλαμβάνει πολλά στοίβα πιέζει και το σκάσιμο, το οποίο είναι πιο αργή από ό, τι looping. Νομίζω ότι μερικές γλώσσες χειριστεί καλύτερα από τους άλλους, και αυτές οι γλώσσες είναι πιο πιθανό να μην εκείνες όπου το κυρίαρχο πρότυπο είναι διαδικαστική ή αντικειμενοστρεφή.

  4. Για τουλάχιστον μια-δυο γλώσσες προγραμματισμού που έχω χρησιμοποιήσει, θυμάμαι συστάσεις ακοής να μην χρησιμοποιούν αναδρομή εάν παίρνει πέρα ​​από ένα ορισμένο βάθος, διότι stack του δεν είναι και τόσο βαθιά.

Απαντήθηκε 06/08/2008 στις 04:12
πηγή χρήστη

ψήφοι
4

1.) Μια μέθοδος είναι αναδρομική αν μπορεί να καλέσει? είτε άμεσα:

void f() {
   ... f() ... 
}

ή έμμεσα:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Όταν στη χρήση της αναδρομής

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) Οι άνθρωποι χρησιμοποιούν αναδρομή μόνο όταν είναι πολύ περίπλοκο να γράψει επαναληπτική κώδικα. Για παράδειγμα, οι τεχνικές δέντρου διάσχισης, όπως προ-παραγγελία, postorder μπορεί να γίνει τόσο επαναληπτική και αναδρομική. Αλλά συνήθως χρησιμοποιούμε αναδρομική λόγω της απλότητάς του.

Απαντήθηκε 11/03/2014 στις 10:47
πηγή χρήστη

ψήφοι
4

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

Για παράδειγμα, πάρτε παραγοντικό:

factorial(6) = 6*5*4*3*2*1

Αλλά είναι εύκολο να δει παραγοντικού (6) και είναι:

6 * factorial(5) = 6*(5*4*3*2*1).

Έτσι, σε γενικές γραμμές:

factorial(n) = n*factorial(n-1)

Φυσικά, το δύσκολο πράγμα για αναδρομής είναι ότι αν θέλετε να ορίσετε τα πράγματα από την άποψη του τι έχετε ήδη κάνει, θα πρέπει να υπάρχει κάποια θέση για να ξεκινήσουμε από εκεί.

Σε αυτό το παράδειγμα, εμείς απλά κάνουμε μια ειδική περίπτωση με τον καθορισμό παραγοντικό (1) = 1.

Τώρα βλέπουμε από κάτω προς τα πάνω:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Από τη στιγμή που ορίζεται παραγοντικού (1) = 1, φτάνουμε στην «κάτω».

Σε γενικές γραμμές, αναδρομικές διαδικασίες έχουν δύο μέρη:

1) Το επαναληπτικό τμήμα, το οποίο ορίζει κάποια διαδικασία όσον αφορά τις νέες εισόδους σε συνδυασμό με αυτό που έχετε «ήδη κάνει» με την ίδια διαδικασία. (δηλαδή factorial(n) = n*factorial(n-1))

2) Ένα τμήμα βάσης, η οποία εξασφαλίζει ότι η διαδικασία δεν επαναλαμβάνεται πάντα δίνοντάς του κάποιο μέρος για να ξεκινήσετε (δηλαδή factorial(1) = 1)

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

Η ελπίδα αυτό βοηθά ...

Απαντήθηκε 04/05/2010 στις 14:30
πηγή χρήστη

ψήφοι
4

Μου αρέσει αυτό τον ορισμό:
Σε αναδρομή, μια ρουτίνα λύνει ένα μικρό μέρος του ίδιου προβλήματος, διαιρεί το πρόβλημα σε μικρότερα κομμάτια, και στη συνέχεια καλεί τον εαυτό της για την επίλυση κάθε ένα από τα μικρότερα κομμάτια.

Μου αρέσει επίσης ο Steve McConnells συζήτηση αναδρομή στον Κώδικα Συμπληρώστε όπου επικρίνει τα παραδείγματα που χρησιμοποιούνται στην Επιστήμη των Υπολογιστών βιβλία για Αναδρομή.

Μην χρησιμοποιείτε αναδρομή για παραγοντικών ή αριθμούς Fibonacci

Ένα πρόβλημα με τον υπολογιστή-επιστήμη εγχειρίδια είναι ότι παρουσιάζουν ανόητα παραδείγματα της αναδρομής. Τα τυπικά παραδείγματα υπολογισμό ενός παραγοντικό ή τον υπολογισμό ενός ακολουθία Fibonacci. Αναδρομή είναι ένα ισχυρό εργαλείο, και είναι πραγματικά χαζό να το χρησιμοποιήσετε σε καμία από αυτές τις περιπτώσεις. Αν ένας προγραμματιστής ο οποίος εργάστηκε για μένα που χρησιμοποιείται αναδρομή για τον υπολογισμό ένα παραγοντικό, θα ήθελα να προσλάβει κάποιον άλλον.

Σκέφτηκα ότι αυτό ήταν ένα πολύ ενδιαφέρον σημείο για την αύξηση και μπορεί να είναι ένας λόγος για τον οποίο αναδρομή είναι συχνά παρεξηγημένη.

EDIT: Αυτή δεν ήταν μια ανασκαφή σε απάντηση Dav της - δεν είχα δει την απάντηση όταν αυτό δημοσιεύτηκε

Απαντήθηκε 04/05/2010 στις 12:29
πηγή χρήστη

ψήφοι
3

Ένα παράδειγμα: Μια αναδρομική ορισμός μιας σκάλας είναι: Μια σκάλα αποτελείται από: - ένα μόνο βήμα και μια σκάλα (αναδρομή) - ή μόνο ένα απλό στάδιο (τερματισμού)

Απαντήθηκε 04/05/2010 στις 14:34
πηγή χρήστη

ψήφοι
3

Λοιπόν, αυτό είναι ένα αρκετά αξιοπρεπή ορισμό που έχετε. Και wikipedia έχει ένα καλό ορισμό πάρα πολύ. Γι 'αυτό θα προσθέσω άλλο ένα (ίσως χειρότερα) ορισμός για εσάς.

Όταν οι άνθρωποι αναφέρονται σε «αναδρομή», από όπου και αν συνήθως μιλάμε για μια λειτουργία που έχετε γράψει η οποία αυτοαποκαλείται επανειλημμένα μέχρι να γίνει με το έργο του. Αναδρομή μπορεί να είναι χρήσιμο όταν διέρχονται από τις ιεραρχίες στις δομές δεδομένων.

Απαντήθηκε 04/05/2010 στις 12:27
πηγή χρήστη

ψήφοι
3

Για να recurse σε λυθεί το πρόβλημα: δεν κάνουν τίποτα, τελειώσατε.
Για να recurse σε ένα ανοικτό πρόβλημα: να κάνει το επόμενο βήμα, τότε recurse για τα υπόλοιπα.

Απαντήθηκε 06/08/2008 στις 04:32
πηγή χρήστη

ψήφοι
2

Αυτό είναι ένα παλιό θέμα, αλλά θέλω να προσθέσω μια απάντηση από υλικοτεχνική άποψη (δηλαδή όχι από το σημείο αλγόριθμο ορθότητα της άποψης ή άποψη απόδοσης).

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

Έτσι, συχνά αποφεύγουν αναδρομής, και λειτουργία χρήση στοίβα αντί, επειδή η ίδια αναδρομή είναι ουσιαστικά μια λειτουργία στοίβας.

Απαντήθηκε 30/08/2014 στις 11:09
πηγή χρήστη

ψήφοι
2

Μια αναδρομική συνάρτηση είναι μια συνάρτηση που περιέχει μια κλήση στον εαυτό του. Μια αναδρομική struct είναι ένα struct που περιέχει ένα παράδειγμα της ίδιας. Μπορείτε να συνδυάσετε και τα δύο ως αναδρομική τάξη. Το βασικό μέρος ενός αναδρομικού στοιχείο είναι ότι περιέχει ένα στιγμιότυπο / κλήση από μόνη της.

Σκεφτείτε δύο καθρέφτες που αντιμετωπίζει ο ένας τον άλλον. Έχουμε δει την τακτοποιημένη άπειρο φαινόμενο που κάνουν. Κάθε αντανάκλαση είναι ένα στιγμιότυπο από έναν καθρέφτη, ο οποίος περιέχεται μέσα σε ένα άλλο παράδειγμα από έναν καθρέφτη, κλπ Το κάτοπτρο που περιέχει μια αντανάκλαση της ίδιας είναι αναδρομής.

Ένα δυαδικό δένδρο αναζήτησης είναι ένα καλό παράδειγμα προγραμματισμού της αναδρομής. Η δομή έχει επαναληπτικό με κάθε κόμβο που περιέχει 2 παρουσίες ενός κόμβου. Λειτουργίες για να εργαστούν σε ένα δυαδικό δέντρο αναζήτησης είναι επίσης αναδρομική.

Απαντήθηκε 04/05/2010 στις 17:46
πηγή χρήστη

ψήφοι
2

Με απλά λόγια: Ας υποθέσουμε ότι μπορείτε να κάνετε 3 πράγματα:

  1. Πάρτε ένα μήλο
  2. Γράψτε κάτω τα σήματα ψηλά
  3. Μετρήστε τα σήματα ψηλά

Έχετε πολλά μήλα μπροστά σας σε ένα τραπέζι και θέλετε να μάθετε πόσα μήλα είναι εκεί.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

Η διαδικασία επαναλαμβάνοντας το ίδιο πράγμα μέχρι να τελειώσετε ονομάζεται αναδρομή.

Ελπίζω ότι αυτό είναι το «απλά αγγλικά» απάντηση που ψάχνετε!

Απαντήθηκε 04/05/2010 στις 14:09
πηγή χρήστη

ψήφοι
1

Ο πιο απλός ορισμός της αναδρομής είναι η «αυτο-αναφοράς». Μια λειτουργία που αναφέρεται στο ίδιο, δηλαδή αυτοαποκαλείται έχει επαναληπτικό. Το πιο σημαντικό πράγμα που πρέπει να θυμάστε, είναι ότι μια αναδρομική συνάρτηση πρέπει να έχει ένα «βασικό σενάριο», δηλαδή μια κατάσταση που αν αληθεύει προκαλεί να μην αυτοαποκαλείται, και έτσι να τερματίσει την αναδρομή. Διαφορετικά θα έχετε άπειρη αναδρομή:

αναδρομή http://cart.kolix.de/wp-content/uploads/2009/12/infinite-recursion.jpg

Απαντήθηκε 04/05/2010 στις 17:10
πηγή χρήστη

ψήφοι
1

Αναδρομή είναι όταν έχετε μια επιχείρηση που χρησιμοποιεί η ίδια. Κατά πάσα πιθανότητα θα έχει ένα σημείο στάσης, διαφορετικά θα συνεχιστεί επ 'αόριστον.

Ας υποθέσουμε ότι θέλετε να αναζητήσετε μια λέξη στο λεξικό. Έχετε μια λειτουργία που ονομάζεται «look-up» στη διάθεσή σας.

Ο φίλος σας λέει ότι «θα μπορούσα πραγματικά κουτάλι κάποια πουτίγκα τώρα!» Δεν ξέρω τι σημαίνει, έτσι ώστε να κοιτάζω προς τα πάνω «κουτάλι» στο λεξικό και διαβάζει κάτι σαν αυτό:

Spoon: ουσιαστικό - ένα σκεύος με στρογγυλό σέσουλα στο τέλος. Spoon: ρήμα - για να χρησιμοποιήσετε ένα κουτάλι για κάτι κουτάλι: ρήμα - να αγκαλιάσει στενά από πίσω

Τώρα, είναι ότι δεν είστε πραγματικά καλός με τα αγγλικά, αυτό που δείχνει προς τη σωστή κατεύθυνση, αλλά θα πρέπει να έχετε περισσότερες πληροφορίες. Έτσι, μπορείτε να επιλέξετε «σκεύος» και «αγκαλιά» να ψάξουν για κάποιο περισσότερες πληροφορίες.

Αγκαλιά: ρήμα - να χώνομαι σκεύος: ουσιαστικό - ένα εργαλείο, συχνά ένα σκεύος φαγητού

Γεια σου! Ξέρεις τι σύσφιγξη είναι, και δεν έχει τίποτα να κάνει με την πουτίγκα. Μπορείτε επίσης να γνωρίζετε ότι η πουτίγκα είναι κάτι που τρώτε, έτσι έχει νόημα τώρα. Ο φίλος σας πρέπει να θέλουν να φάνε πουτίγκα με ένα κουτάλι.

Εντάξει, εντάξει, αυτό ήταν ένα πολύ κουτσός παράδειγμα, αλλά επεξηγεί (ίσως κακώς) τα δύο κύρια μέρη της αναδρομής. 1) χρησιμοποιεί η ίδια. Σε αυτό το παράδειγμα, δεν έχετε πραγματικά κοίταξε μια λέξη με νόημα μέχρι να το καταλάβετε, και αυτό μπορεί να σημαίνει την αναζήτηση περισσότερες λέξεις. Αυτό μας φέρνει στο σημείο δύο, 2) σταματά κάπου. Πρέπει να έχουν κάποιο είδος της βάσης περίπτωση. Διαφορετικά, θα καταλήξετε ακριβώς ψάχνει κάθε λέξη στο λεξικό, το οποίο κατά πάσα πιθανότητα δεν είναι πάρα πολύ χρήσιμη. base-περίπτωσή μας ήταν ότι έχεις αρκετές πληροφορίες για να κάνει μια σύνδεση ανάμεσα σε αυτό που προηγουμένως είχε και δεν καταλαβαίνουν.

Το παραδοσιακό παράδειγμα που έχει δοθεί είναι παραγοντικό, όπου 5 παραγοντικό είναι 1 * 2 * 3 * 4 * 5 (το οποίο είναι 120). Η βασική περίπτωση θα είναι 0 (ή 1, ανάλογα). Έτσι, για κάθε ακέραιο αριθμό n, μπορείτε να κάνετε τα εξής

είναι η ίσο με 0; επιστρέψουν 1 Αλλιώς, επιστρέφουν n * (παραγοντικό n-1)

ας το κάνουμε αυτό με το παράδειγμα 4 (το οποίο ξέρουμε εκ των προτέρων είναι 1 * 2 * 3 * 4 = 24).

παραγοντικό 4 ... είναι 0; όχι, γι 'αυτό πρέπει να είναι 4 * παραγοντικό 3, αλλά αυτό που είναι παραγοντικό 3; είναι 3 * παραγοντικό 2 παραγοντικό 2 είναι 2 * παραγοντικό 1 παραγοντικό 1 είναι 1 * παραγοντικό 0 και γνωρίζουμε παραγοντικό 0! :-D είναι 1, αυτό είναι το παραγοντικό ορισμός του 1 είναι 1 * παραγοντικό 0, η οποία ήταν 1 ... έτσι 1 * 1 = 1 παραγοντικό 2 είναι 2 * παραγοντικό 1, η οποία ήταν 1 ... έτσι 2 * 1 = 2 παραγοντικό 3 είναι 3 * παραγοντικό 2, η οποία ήταν 2 ... έτσι 3 * 2 = 6 παραγοντικό 4 (επιτέλους !!) είναι 4 * παραγοντικό 3, η οποία ήταν 6 ... 4 * 6 είναι 24

Παραγοντικό είναι μια απλή περίπτωση της «βασική περίπτωση, και χρησιμοποιεί το ίδιο».

Τώρα, παρατηρήστε μας εξακολουθεί να εργάζεται για παραγοντικό 4 ολόκληρη η διαδρομή ... Αν θέλαμε παραγοντικό του 100, θα έπρεπε να πάει σε όλη τη διαδρομή μέχρι 0 ... το οποίο θα μπορούσε να έχει πολύ γενικά σε αυτό. Με τον ίδιο τρόπο, αν βρούμε μια σκοτεινή λέξη για να αναζητήσετε στο λεξικό, μπορεί να χρειαστούν αναζητούν άλλα λόγια και σάρωση για ενδείξεις πλαίσιο μέχρι να βρούμε μια σύνδεση είμαστε εξοικειωμένοι με. Αναδρομική μέθοδοι μπορεί να πάρει πολύ χρόνο για να συνεχίσουν την πορεία τους μέσα. Ωστόσο, όταν είναι χρησιμοποιούνται σωστά και κατανοητά, μπορούν να κάνουν περίπλοκες εργασίες εκπληκτικά απλή.

Απαντήθηκε 04/05/2010 στις 17:04
πηγή χρήστη

ψήφοι
1

Πάρα πολλά προβλήματα μπορεί να θεωρηθεί σε δύο τύπους κομμάτια:

  1. Βάση περιπτώσεις, οι οποίες είναι στοιχειώδη πράγματα που μπορείτε να λύσετε με απλά κοιτάζοντας τους, και
  2. Αναδρομικές περιπτώσεις, οι οποίες χτίσει ένα μεγαλύτερο πρόβλημα από μικρότερα κομμάτια (δημοτικό ή με άλλο τρόπο).

Έτσι, αυτό είναι μια αναδρομική συνάρτηση; Λοιπόν, αυτό είναι όπου μπορείτε να έχετε μια συνάρτηση που ορίζεται από την άποψη της ίδιας, άμεσα ή έμμεσα. Εντάξει, αυτό ακούγεται γελοίο, μέχρι να συνειδητοποιήσει ότι είναι λογικό για τα προβλήματα του είδους που περιγράφεται παραπάνω: να λύσει τις υποθέσεις βάσης άμεσα και να ασχοληθεί με τις αναδρομικές περιπτώσεις με τη χρήση αναδρομικών κλήσεων για την επίλυση των μικρότερα κομμάτια του προβλήματος εντάσσεται στο πλαίσιο.

Το πραγματικά κλασικό παράδειγμα για το πού θα πρέπει να έχετε αναδρομή (ή κάτι που μυρίζει πολύ σαν αυτό) είναι όταν έχουμε να κάνουμε με ένα δέντρο. Τα φύλλα του δέντρου είναι η βασική περίπτωση, και οι κλάδοι είναι η αναδρομική περίπτωση. (Στην ψευδο-C.)

struct Tree {
    int leaf;
    Tree *leftBranch;
    Tree *rightBranch;
};

Ο απλούστερος τρόπος για να εκτυπώσετε αυτό έξω για να χρησιμοποιήσετε αναδρομή:

function printTreeInOrder(Tree *tree) {
    if (tree->leftBranch) {
        printTreeInOrder(tree->leftBranch);
    }
    print(tree->leaf);
    if (tree->rightBranch) {
        printTreeInOrder(tree->rightBranch);
    }
}

Είναι νεκρός εύκολο να δούμε ότι αυτό πρόκειται να λειτουργήσει, δεδομένου ότι είναι πεντακάθαρη. (Η μη αναδρομική ισοδύναμο είναι πολύ πολύ πιο περίπλοκη, απαιτεί μια δομή στοίβας εσωτερικά για να διαχειριστείτε τη λίστα των πραγμάτων για να επεξεργαστεί.) Λοιπόν, αν υποτεθεί ότι κανείς δεν έχει κάνει μια κυκλική σύνδεση του μαθήματος.

Από μαθηματική άποψη, το τέχνασμα για να δείχνουν ότι η αναδρομή δαμάζεται είναι να επικεντρωθεί στην εξεύρεση μέτρηση για το μέγεθος των επιχειρημάτων. Για παράδειγμα, το δέντρο μας, ο ευκολότερος μετρική είναι το μέγιστο βάθος του δέντρου κάτω από τον τρέχοντα κόμβο. Σε φύλλα, είναι μηδενική. Σε ένα κατάστημα αφήνει μόνο κάτω από αυτό, είναι ένα, κ.λπ. Στη συνέχεια, μπορείτε να δείξετε απλώς ότι υπάρχει είναι αυστηρά διατεταγμένη ακολουθία για το μέγεθος των επιχειρημάτων ότι η λειτουργία γίνεται επίκληση στη θέση του για να επεξεργαστεί το δέντρο? τα επιχειρήματα των αναδρομικών κλήσεων είναι πάντα «μικρότερο», με την έννοια της μετρικής από ό, τι το επιχείρημα για τη συνολική κλήση. Με μια γνησίως φθίνουσα καρδινάλιος μετρικό, είστε ταξινομημένο.

Είναι επίσης δυνατόν να έχουμε άπειρες αναδρομή. Αυτό είναι βρώμικο και σε πολλές γλώσσες δεν θα λειτουργήσει, επειδή η στοίβα ανατιναχθεί. (Σε περίπτωση που το κάνει το έργο, η γλώσσα του κινητήρα πρέπει να τον προσδιορισμό ότι η λειτουργία κατά κάποιο τρόπο δεν επιστρέφει και είναι σε θέση, επομένως, να βελτιστοποιήσει μακριά την τήρηση της στοίβας Tricky πράγματα σε γενικές γραμμές?. Ουρά-αναδρομή είναι μόνο το πιο ασήμαντο τρόπο για να γίνει αυτό .)

Απαντήθηκε 04/05/2010 στις 16:29
πηγή χρήστη

ψήφοι
1

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

Για παράδειγμα

n! = n(n-1)(n-2)(n-3)...........*3*2*1

Τώρα μπορεί να ορίζεται αναδρομικά ως εξής: -

n! = n(n-1)!   for n>=1

Όσον αφορά τον προγραμματισμό, όταν η ίδια η λειτουργία ή η μέθοδος απαιτεί κατ 'επανάληψη, μέχρι κάποια συγκεκριμένη κατάσταση παίρνει ικανοποιημένοι, η διαδικασία αυτή ονομάζεται Αναδρομή. Αλλά πρέπει να υπάρχει μια κατάσταση τερματισμού και λειτουργία ή η μέθοδος δεν πρέπει να τεθεί σε ένα άπειρο βρόχο.

Απαντήθηκε 04/05/2010 στις 16:22
πηγή χρήστη

ψήφοι
1

Η αναδρομή στην πληροφορική είναι μια τεχνική που χρησιμοποιείται για τον υπολογισμό ένα αποτέλεσμα ή παρενέργεια που ακολουθεί την κανονική απόδοση από μια ενιαία λειτουργία (μέθοδος, διαδικασία ή μπλοκ) επίκλησης.

Η αναδρομική συνάρτηση, εξ ορισμού πρέπει να έχει τη δυνατότητα να επικαλεστεί η ίδια, είτε άμεσα είτε έμμεσα (μέσω άλλων λειτουργιών), ανάλογα με την κατάσταση εξόδου ή προϋποθέσεις δεν πληρούνται. Αν μια συνθήκη εξόδου πληρούσαν τα συγκεκριμένα επίκληση επιστρέφει στην καλούντα να είναι. Αυτό συνεχίζεται έως ότου η αρχική επίκληση επιστρέφεται από, κατά τον οποίο χρόνο θα είναι διαθέσιμο το επιθυμητό αποτέλεσμα ή παρενέργεια.

Για παράδειγμα, εδώ είναι μια λειτουργία για να εκτελέσει τον αλγόριθμο Quicksort στη Σκάλα ( αντιγραφή από την καταχώρηση της Wikipedia για Scala )

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

Σε αυτή την περίπτωση η κατάσταση εξόδου είναι μια κενή λίστα.

Απαντήθηκε 04/05/2010 στις 15:14
πηγή χρήστη

ψήφοι
1

Λειτουργία ίδια καλέσετε ή να χρησιμοποιήσει δικό της ορισμό.

Απαντήθηκε 04/05/2010 στις 14:59
πηγή χρήστη

ψήφοι
1

Κάθε αλγόριθμος παρουσιάζει διαρθρωτικές αναδρομή σε ένα τύπο δεδομένων και αν ουσιαστικά αποτελείται από ένα διακόπτη-δήλωση με την περίπτωση, για κάθε περίπτωση τύπο δεδομένων.

Για παράδειγμα, όταν εργάζεστε σε έναν τύπο

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

ένα δομικό αναδρομικό αλγόριθμο που θα έχει τη μορφή

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

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

τώρα, εάν κοιτάξει κανείς τους ακέραιους αριθμούς (καλά, οι φυσικοί αριθμοί), όπως ορίζεται με τα αξιώματα Peano

 integer = 0 | succ(integer)

θα δείτε ότι ένα δομικό αναδρομικό αλγόριθμο για ακέραιους μοιάζει με αυτό

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

το πολύ-γνωστό παραγοντικό λειτουργία είναι για το πιο ασήμαντο παράδειγμα αυτής της μορφής.

Απαντήθηκε 04/05/2010 στις 14:53
πηγή χρήστη

ψήφοι
1

Γεια σου, συγγνώμη αν τη γνώμη μου συμφωνεί με κάποιον, είμαι απλώς προσπαθεί να εξηγήσει αναδρομή σε απλά αγγλικά.

ας υποθέσουμε ότι έχετε τρεις διευθυντές - Jack, John και Morgan. Ο Jack καταφέρνει 2 προγραμματιστές, John - 3, και Morgan - 5. πρόκειται να δώσει σε κάθε διαχειριστή 300 $ και θέλετε να μάθετε τι θα κοστίσει. Η απάντηση είναι προφανής - αλλά τι γίνεται αν 2 των εργαζομένων Morgan-s είναι επίσης διαχειριστές;

Εδώ έρχεται η αναδρομή. που ξεκινούν από την κορυφή της ιεραρχίας. το καλοκαιρινό κόστος είναι 0 $. μπορείτε να ξεκινήσετε με τον Jack, Στη συνέχεια, ελέγξτε αν έχει κάποια στελέχη, όπως οι εργαζόμενοι. αν βρείτε κάποιο από αυτά, ελέγξτε εάν έχουν διευθυντές και τους υπαλλήλους και ούτω καθεξής. Προσθέστε 300 $ στο καλοκαιρινό κόστος κάθε φορά που θα βρείτε έναν διαχειριστή. όταν τελειώσετε με τον Jack, να πάει στον Ιωάννη, τους υπαλλήλους του και στη συνέχεια να Morgan.

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

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

Απαντήθηκε 04/05/2010 στις 13:50
πηγή χρήστη

ψήφοι
1

Με απλά λόγια, αναδρομή σημαίνει να επαναλάβει ξανά και ξανά someting.

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

Δείτε στο παρακάτω παράδειγμα υπολογισμού παραγοντικό ενός αριθμού:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
Απαντήθηκε 04/05/2010 στις 13:48
πηγή χρήστη

ψήφοι
1

Αναδρομή είναι η διαδικασία κατά την οποία μια κλήση μεθόδου iself να είναι σε θέση να εκτελέσει μια συγκεκριμένη εργασία. Μειώνει Redundency του κώδικα. Οι περισσότεροι recurssive λειτουργίες ή μέθοδοι πρέπει να έχουν condifiton να σπάσει το recussive αποκαλούν, δηλαδή να σταματήσει αυτό από αυτοαποκαλείται αν μια συνθήκη πληρούται - αυτό εμποδίζει τη δημιουργία ενός άπειρου βρόχου. Δεν είναι όλες οι λειτουργίες κατάλληλες για να χρησιμοποιηθούν κατ 'επανάληψη.

Απαντήθηκε 04/05/2010 στις 13:42
πηγή χρήστη

ψήφοι
1

ένας τρόπος του να κάνουμε πράγματα ξανά και ξανά επ 'αόριστον έτσι ώστε να χρησιμοποιείται κάθε επιλογή.

Για παράδειγμα, αν θέλετε να πάρετε όλες τις συνδέσεις σε μια σελίδα HTML θα θέλετε να έχετε επαναλήψεις, γιατί όταν θα έχετε όλες τις συνδέσεις στη σελίδα 1 θα θέλετε να πάρετε όλες τις συνδέσεις για κάθε μία από τις συνδέσεις που βρέθηκαν στην πρώτη σελίδα. Στη συνέχεια για κάθε σύνδεση με μια νέα σελίδα που θα θέλετε αυτές τις συνδέσεις και ούτω καθεξής ... με άλλα λόγια, είναι μια λειτουργία που αυτοαποκαλείται μέσα από την ίδια.

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

σε C # θα έχετε κάτι σαν αυτό:

private void findlinks(string URL, int reccursiveCycleNumb)    {
   if (reccursiveCycleNumb == 0)
        {
            return;
        }

        //recursive action here
        foreach (LinkItem i in LinkFinder.Find(URL))
        {
            //see what links are being caught...
            lblResults.Text += i.Href + "<BR>";

            findlinks(i.Href, reccursiveCycleNumb - 1);
        }

        reccursiveCycleNumb -= reccursiveCycleNumb;
}
Απαντήθηκε 04/05/2010 στις 13:02
πηγή χρήστη

ψήφοι
1

«Αν έχω ένα σφυρί, κάνουν τα πάντα μοιάζουν με ένα καρφί.»

Αναδρομή είναι μια στρατηγική επίλυσης προβλημάτων για την τεράστια προβλήματα, όπου σε κάθε βήμα ακριβώς, «γυρίστε 2 μικρά πράγματα σε ένα μεγαλύτερο πράγμα,» κάθε φορά με το ίδιο σφυρί.

Παράδειγμα

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

  1. Χάσμα: Απλώστε όλα τα φύλλα έξω, έτσι ώστε να έχετε μόνο ένα φύλλο σε κάθε «στοίβα».
  2. Κατακτώ:
    1. Πηγαίνετε γύρω, βάζοντας κάθε φύλλο το ένα πάνω στο άλλο φύλλο. Τώρα έχετε στοίβες των 2.
    2. Πηγαίνετε γύρω, βάζοντας κάθε 2-στοίβα πάνω στο άλλο 2-stack. Τώρα έχετε στοίβες των 4.
    3. Πηγαίνετε γύρω, βάζοντας κάθε 4-στοίβα πάνω στο άλλο 4-stack. Τώρα έχετε στοίβες των 8.
    4. ... ξανά και ξανά ...
    5. Τώρα έχετε μια τεράστια στοίβα από 1024 φύλλα!

Σημειώστε ότι αυτό είναι αρκετά έξυπνο, εκτός από την καταμέτρηση τα πάντα (που δεν είναι απολύτως απαραίτητα). Μπορεί να μην πάει σε όλη τη διαδρομή μέχρι στοίβες 1-φύλλο, στην πραγματικότητα, αλλά θα μπορούσε και θα εξακολουθούν να εργάζονται. Το σημαντικό κομμάτι είναι το σφυρί: Με τα χέρια σας, μπορείτε να βάλετε πάντα μια στοίβα πάνω από το άλλο για να κάνει ένα μεγαλύτερο stack, και δεν έχει σημασία (σε λογικά πλαίσια) πόσο μεγάλο είναι είτε στοίβα είναι.

Απαντήθηκε 04/05/2010 στις 12:54
πηγή χρήστη

ψήφοι
1

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

Απαντήθηκε 04/05/2010 στις 12:25
πηγή χρήστη

ψήφοι
1

Θέλετε να το χρησιμοποιήσετε οποιαδήποτε στιγμή έχετε μια δομή δέντρου. Είναι πολύ χρήσιμο στην ανάγνωση XML.

Απαντήθηκε 21/08/2008 στις 14:18
πηγή χρήστη

ψήφοι
1

Mario, δεν καταλαβαίνω γιατί χρησιμοποιείται αναδρομή για το συγκεκριμένο παράδειγμα .. Γιατί να μην απλά περάστε μέσα από κάθε καταχώρηση; Κάτι σαν αυτό:

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

Η παραπάνω μέθοδος θα είναι ταχύτερη, και είναι απλούστερη. Δεν υπάρχει καμία ανάγκη να χρησιμοποιήσει αναδρομή στη θέση ενός απλού βρόχου. Νομίζω ότι αυτά τα είδη των παραδειγμάτων είναι ο λόγος αναδρομή παίρνει μια κακή ραπ. Ακόμη και η κανονική παραγοντικό παράδειγμα η λειτουργία να εφαρμοστεί καλύτερα με ένα βρόχο.

Απαντήθηκε 06/08/2008 στις 04:19
πηγή χρήστη

ψήφοι
0

Στην πραγματικότητα η καλύτερη αναδρομική λύση για παραγοντικό πρέπει να είναι:

int factorial_accumulate(int n, int accum) {
    return (n < 2 ? accum : factorial_accumulate(n - 1, n * accum));
}

int factorial(int n) {
    return factorial_accumulate(n, 1);
}

Επειδή αυτή η έκδοση είναι η ουρά Αναδρομικές

Απαντήθηκε 21/08/2008 στις 14:39
πηγή χρήστη

ψήφοι
0

Χρησιμοποιώ αναδρομή. Τι σημαίνει ότι έχουν να κάνουν με την κατοχή ενός βαθμού CS ... (το οποίο εγώ δεν κάνω, από τον τρόπο)

Κοινές χρήσεις που έχω βρεθεί:

  1. sitemaps - recurse μέσω σύστημα αρχείων που ξεκινούν από ρίζας εγγράφου
  2. αράχνες - σέρνεται μέσα από μια ιστοσελίδα για να βρείτε τη διεύθυνση ηλεκτρονικού ταχυδρομείου, συνδέσεις, κ.λπ.
  3. ;
Απαντήθηκε 06/08/2008 στις 04:13
πηγή χρήστη

ψήφοι
0

Έχω δημιουργήσει μια αναδρομική συνάρτηση για να ενώσετε μια λίστα με τις χορδές με ένα διαχωριστικό μεταξύ τους. Το χρησιμοποιώ κυρίως για τη δημιουργία εκφράσεις SQL, περνώντας μια λίστα πεδίων, όπως τα « στοιχεία » και ένα « κόμμα + χώρος » ως διαχωριστικό. Εδώ είναι η συνάρτηση (Χρησιμοποιεί κάποιες Borland Builder τύπους εσωτερικά δεδομένα, αλλά μπορεί να προσαρμοστεί σε οποιοδήποτε άλλο περιβάλλον):

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

Θα το ονομάσουμε αυτό τον τρόπο:

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

Φανταστείτε ότι έχετε μια σειρά που ονομάζεται « πεδία » με αυτά τα δεδομένα μέσα σε αυτό: « ALBUMNAME », « releasedate », « labelId ». Στη συνέχεια, μπορείτε να καλέσετε τη συνάρτηση:

ArrangeString(fields, 0, ", ");

Καθώς η λειτουργία αρχίζει να λειτουργεί, η μεταβλητή « αποτέλεσμα » δέχεται την αξία της θέσης 0 του πίνακα, το οποίο είναι « ALBUMNAME ».

Στη συνέχεια ελέγχει αν η θέση είναι που ασχολούνται με είναι η τελευταία. Δεδομένου ότι δεν είναι, τότε θα συνδέει το αποτέλεσμα με το διαχωριστικό και το αποτέλεσμα της συνάρτησης, η οποία, ω Θεέ, είναι αυτή η ίδια λειτουργία. Αλλά αυτή τη φορά, να δεις, να αυτοαποκαλείται προσθήκη 1 στη θέση.

ArrangeString(fields, 1, ", ");

Διατηρεί την επανάληψη, δημιουργώντας ένα σωρό LIFO, μέχρι να φτάσει σε ένα σημείο όπου η θέση που εξετάζονται είναι η τελευταία, οπότε η συνάρτηση επιστρέφει μόνο το στοιχείο σε αυτή τη θέση στη λίστα, δεν συνενώσει πια. Στη συνέχεια, ο σωρός είναι συνεχόμενα προς τα πίσω.

Το κατάλαβα? Αν δεν το κάνετε, δεν έχω άλλο τρόπο να το εξηγήσω. : O)

Απαντήθηκε 06/08/2008 στις 04:00
πηγή χρήστη

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more