Αναδρομη στον προγραμματισμο

[alexc]

Θα ηθελα να ρωτησω τους πιο εμπειρους  εδω μεσα αν ειναι καποιος fan της αναδρομης και που εξυπηρετει πιο καλα σε σχεση με την επαναληψη..... Υπαρχει καποιο προβλημα που να επλυεται μονο με αυτη η μας βασανιζουν αδικα στην σχολη και ισως μου στερησουν ενα χρονο αδικα.... Ειναι τοσο σημαντικη  στην μετεπειτα πορεια ενος προγραμματιστη η απλα απο τα 100 προβληματα που θα εχει να λυσει η 1 ισως λυνεται με αναδρομη.... Τα λεω αυτα μεσα στο αγχος μου και την στεναχωρια μου που εφαγα αδικα ολη την ωρα της εξετασης προσπαθωντας να επιλυσω ενα τετοιο προβλημα,βγαζοντας την τελικα αλλα με λαθος.....

[albNik]

Το πιο κλασικό παράδειγμα είναι να διατρέξεις ένα δέντρο.

 

Π.χ. έχεις μια δομή από καταλόγους και αρχεία και θες να επέμβεις στα αρχεία. Ένα παράδειγμα σε C# :

 void DirSearch(string sDir)
 {         
        foreach(string filename in Directory.GetFiles(sDir))
        {
           // do something with the file 
        }
        foreach(string d in Directory.GetDirectories(sDir)) 
            DirSearch(d); 
 }

[georgemarios]

Θεωρητικά, οτι γινεται με αναδρομη, μπορει να γινει και με επαναληψη (λεω θεωρητικα κρατωντας παντα επιφυλλαξη γιατι δε εχω δει ποτε περιπτωση που δε γινεται)

 

Η αναδρομη ειναι λιγοτερο αποτελεσματικη (λογω σπαταλης μνημης) αλλα υπαρχουν ατομα που υποστηριζουν πως ειναι πιο ευαναγνωστη (ανηκω στην αντιθετη αποψη)

[kagelos]

Και γω νόμιζα πως θα κάναμε ιστορική αναδρομή

[bird]

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

 

Για παράδειγμα τον quicksort, δεν έχω σκεφτεί ποτέ να τον υλοποιήσω χωρίς αναδρομή...

[nilosgr]

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

 

Αποψη μου, στοχος της αναδρομης ειναι να μαθεις εναν διαφορετικο τροπο σκεψης. Στην ουσια η ναδρομη ειναι η 'βαση' του divide and conquer, οποτε ναι ειναι σημαντικη και χρησημη. Το οτι καποιο προβλημα λυνετε και με αναδρομη και με επαναληψη δεν σημαινει οτι η επαναληψη θα ειναι 'πιο απλη' ( πχ οι πυργοι του Ανοη ειναι κλασικο προβλημα που χρειαζεσαι αναδρομικη σκεψη για να καταλαβεις/βρεις τη λυση ). Τελος εισαι πανεπιστημιο, θα γινεις επιστημονας, οχι απλος εργατης που απλα θα εφαρμοζεις αυτα που σου λενε, θεωρητικα θα πρεπει και να δημιουργεις γνωση.

 

Σορι, αλλα το ολο ποστ μου θυμησε το "Εγω ειμαι θεωρητικη κατευθυνση, γιατι να μαθω οτι (x²)' = 2x ??!!"

 

[defacer]

Θα ηθελα να ρωτησω τους πιο εμπειρους  εδω μεσα αν ειναι καποιος fan της αναδρομης και που εξυπηρετει πιο καλα σε σχεση με την επαναληψη..... Υπαρχει καποιο προβλημα που να επλυεται μονο με αυτη η μας βασανιζουν αδικα στην σχολη και ισως μου στερησουν ενα χρονο αδικα.... Ειναι τοσο σημαντικη  στην μετεπειτα πορεια ενος προγραμματιστη η απλα απο τα 100 προβληματα που θα εχει να λυσει η 1 ισως λυνεται με αναδρομη.... Τα λεω αυτα μεσα στο αγχος μου και την στεναχωρια μου που εφαγα αδικα ολη την ωρα της εξετασης προσπαθωντας να επιλυσω ενα τετοιο προβλημα,βγαζοντας την τελικα αλλα με λαθος.....

 

Άσε τη στεναχώρια σου στην άκρη γιατί είναι κακός σύμβουλος.

 

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

 

Όμως!

 

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

 

Το ίδιο ισχύει και στον προγραμματισμό. Αν δε μπορείς να καταλάβεις τι σημαίνει αναδρομή τότε δε θα καταλάβεις ποτέ (ή θα "καταλάβεις" τελείως επιφανειακά) πώς λειτουργούν οι divide and conquer αλγόριθμοι, που είναι βασικότατο τμήμα του computer science και όχι μόνο. Μιλάμε για τιτανοαλγόριθμους όπως quicksort, mergesort, FFT και γενικά τους περισσότερους που είναι πολυπλοκότητας O(NlogN). Αν δεν τους κατέχεις απλά πλατσουρίζεις στο ένα μέτρο βάθος και κατά τα άλλα δηλώνεις κολυμβητής.

 

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

 

Functional programming: Δε μπορείς να χρησιμοποιήσεις επανάληψη σε μια αμιγώς functional γλώσσα προγραμματισμού (αναδρομή μπορείς).

 

Parallelization: Οποιοσδήποτε αναδρομικός αλγόριθμος είναι trivially parallelizable, που σημαίνει ότι μπορεί πανεύκολα να αξιοποιήσει πολλαπλούς cores/επεξεργαστές/servers/και δε συμμαζέυεται για να εξάγει το αποτέλεσμά του γρηγορότερα. Ο ίδιος αλγόριθμος με επανάληψη απαιτεί να γράψεις χειροκίνητα και πολύ πολύ προσεκτικά κώδικα για να πετύχεις το ίδιο αποτέλεσμα, σε σημείο που καταλήγεις να κάνεις πολύ περισσότερη δουλειά για το ίδιο αποτέλεσμα. Ένα... κάπως γνωστό μοντέλο προγραμματισμού που βασίζεται σε τέτοιου είδους parallelization είναι το Map/Reduce. Ίσως να έχεις ακουστά μια εταιρία που στήθηκε (ποιητική αδεία) πάνω σ' αυτό το μοντέλο επεξεργασίας δεδομένων, Google τη λένε.

 

Thread safety: Ακόμα κι όταν δεν έχεις ανάγκη τέτοια ιπποδύναμη, σχεδόν πάντα έχεις ανάγκη από κάποιο βαθμό παραλληλοποίησης της επεξεργασίας, που σημαίνει ότι αυτόματα έχεις να λύσεις προβλήματα σχετικά με thread safety. Ένας πολύ απλός τρόπος να γίνει κάτι thread safe είναι να χρησιμοποιείς αμετάβλητες δομές δεδομένων (immutable data structures). Όμως όπως είπαμε παραπάνω, η επανάληψη απαιτεί mutability. Επομένως αυτός ο τρόπος λύσης του προβλήματος του thread safety (που πολλές φορές είναι ο καλύτερος) κόβεται από τη ρίζα εκτός και αν χρησιμοποιήσεις αναδρομή.

 

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

 

Κράξιμο

 

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

 

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

 

 

Θεωρητικά, οτι γινεται με αναδρομη, μπορει να γινει και με επαναληψη (λεω θεωρητικα κρατωντας παντα επιφυλλαξη γιατι δε εχω δει ποτε περιπτωση που δε γινεται)

 

Η αναδρομη ειναι λιγοτερο αποτελεσματικη (λογω σπαταλης μνημης) αλλα υπαρχουν ατομα που υποστηριζουν πως ειναι πιο ευαναγνωστη (ανηκω στην αντιθετη αποψη)

 

Όπως πρέπει να είναι κατανοητό από τα παραπάνω, that is not the point (και επίσης η αναδρομή δε σπαταλάει μνήμη όταν είναι σωστά φτιαγμένη και ο compiler υποστηρίζει tail call optimizations).

 

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

 

Συμπέρασμα:

 

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

[ZAKKWYLDE]

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

[Directx]

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

 

Υ.Γ.

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

[alexc]

Ευχαριστω πολυ ολους σας για τις απαντησεις σας!!!!

Ειδικα τον defacer καθως με καλυψε πληρως...

Αυτο που ηθελα να πω ειναι οτι τα λογια αυτα οντως φανηκαν με τον τροπο που εννοεισες αλλα δεν ηθελα να πιστεψεις κατι τετοιο...

Ειναι το αντικειμενο που γουσταρω πραγματικα και οντας αρχαριος δεν εχω ανακαλυψει ισως την πραγματικη αξια αυτης της τεχνικης καθως οπως καταλαβαινεις σε αυτο το επιπεδο που βρισκομαι μου φαινεται απλα " ε αφου γινεται με επαναληψη γιατι μας παιδευουν"....Με καλυψες πληρως για αυτα που ηθελα να μαθω και με πεισμωνει το γεγονος οτι ακομα δεν την εχω "πιασει πληρως"...

Ευχαριστω και παλι!!!

 

[ZAKKWYLDE]

Θα σου τύχει μελλοντικά αρκετές φορές να πάς να λύσεις ένα πρόβλημα με Iteration και δεν θα βγάζει κανένα νόημα απολύτως, ενώ με αναδρομή θα λύνεται σχεδόν "για πλάκα".

Η αλήθεια βέβαια είναι απο την άλλη ότι στο 90% των περιπτώσεων θα χρησιμοποιείς επανάληψη. Στο 10% που θα χρειαστείς αναδρομή θα είναι υπερπολύτιμη όμως. Ότι μαθαίνεις πάντως είναι χρήσιμο, μην το απορρίπτεις.

 

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

Όμως τα μαθήματα αυτά γίνονται κυρίως για να μάθεις τι συμβαίνει στο lower level κομμάτι(έτσι ώστε να ξέρεις ακριβώς για ποιό λόγο θα χρησιμοποιήσεις Linked List αντί για Array List) αλλά και για να μάθεις να σκέφτεσαι. Οπότε και εκεί μην το απορρίψεις.