recursion h loop?

[pietro]

Hello paidia mia aporia pou mou hr8e grafwntas kwdika gia ton n paragontiko. Estw oti exoume tis idies entoles me thn diafora mono sto oti sthn mia kaleis thn function kai sthn alh gurnas sthn arxh ths for, einai kapoio apo ta duo poio grhgoro? Na dwsw kai ena paradeigma upologizontas to n paragontiko

 

/*me loop*/

factorian(int n)

{

int result = 1;

for(i=2; i < (n-1); i++)

{

result = result * i;

}

returnn result;

}

 

/*me recursion*/

factorian(int n)

{

if (n == 1)

return 1;

else

return factorial(n-1)*n

}

 

thanx

[kostas_crete]

to paragontiko me loop einai pio argo alla 8elei ligoterh mnhmh.

To paragontiko me regression einai pio grhgoro alla apaitei mnhmh arketh gia ola ta stigmiotypa ths factorial.

[pietro]

thanx Giati auto?..

[Red_Phantom]

to paragontiko me loop einai pio argo alla 8elei ligoterh mnhmh.

To paragontiko me regression einai pio grhgoro alla apaitei mnhmh arketh gia ola ta stigmiotypa ths factorial.

 

 

Aplos merikes programmatistikes arxes:

1.H anadromi kostizei poli kai se cpu kai se mnimi.Kathe fora pou kaleitai i sinartisi xreiazetai neo activation record.Yparxoun kai periptoseis me anadromi pou ypologizeis ta idia pragmata polles fores(dentro anadromis).

 

2.Epidei i klisi tis sinartisis kostizei sinartiseis opos abs(x) sgn(x) diladi kanoun liga se sxesei me to kostos kalesmatos tous san sinartiseis,ta ftiaxneis san macros (define ktl).

 

3.H anadromi einai pio eukoli stin katanoisi enos programmatos kai einai pio konta ston anthropo san logiki.Gia na to deis auto skepsou os exeis.

An metonomaseis tis sinatriseis apo factorial se insomnia px kai rotiseis kapoion xoris na xerei ti exeis kanei ,stin anadromi tha katalabei eukola oti ftiaxneis to factorial eno sto allo tha diskoleutei sxetika.

 

 

Sinepos pio grigori kai me ligoteri mnimi einai i ilopoiisi me loop, pio omorfi kai katanoiti i ilopoiisi me anadromi.

[bandito]

Αν είναι να υλοποιήσεις factorial με int , δεν πας πολύ μακριά.

Και long unsigned int να ειναι το πολύ να φτάσεις μέχρι το 21.

Οπότε, υπάρχει μια καθαρή λύση , που τρώει ακριβώς 21 θέσεις μνήμης, και χρειάζεται μόλις ένα κύκλο για να υπολογίσει οποιοδήποτα παραγοντικό μέχρι το 21. Αν και το ίδιο μπορεις να κάνεις για όποιο νούμερο θές (αν χρησιμοποιείς doubles δηλαδη). Look up table

[Turrican]

Αν ψάξεις στο google "recursive vs loop" θα δείς οτι στο 99.9% λένε οτι από άποψη ταχύτητας οι loops είναι *πάντα* γρηγορότερες μεθοδοι ομως πιο δυσνόητες.

 

Αλλά...

 

α. Προσωπικά βρίσκω τις loops ευκολότερα κατανοητές.

β. Μερικοί recursive αλγόριθμοι είναι πολλαπλά γρηγορότεροι από αντίστοιχους με loops - π.χ. δες τις Mergesort και Quicksort - επίσης αν θές διάβασε και αυτό

[xaotikos]

Και εμένα πιο κατανοητά μου φαίνονται τα loops,anyway

 

Χρησιμοποιήσε long doubles για να υπολογίζεις τα factorials...

[bandito]

Αν ψάξεις στο google "recursive vs loop" θα δείς οτι στο 99.9% λένε οτι από άποψη ταχύτητας οι loops είναι *πάντα* γρηγορότερες μεθοδοι ομως πιο δυσνόητες.

 

Αυτό παραείναι γενικό για να ειναι αλήθεια.

Αν μιλάς για ΣΥΓΚΕΚΡΙΜΕΝΟΥΣ αλγόριθμους ' date=' ίσως και να ισχύει.

Διαφορετικά ειναι σαν να λές τα κόκκινα αυτοκίνητα ειναι πάντα γρηγορότερα απο τα πράσινα.

 

Αλλά...

 

α. Προσωπικά βρίσκω τις loops ευκολότερα κατανοητές.

Πάρε το παράδειγμα στο λινκ που δίνεις και αντί για binary tree , βάλε AVL balanced tree με 10 leaves σε κάθε branch. Αν *φτιάξεις* το loop και το καταλάβει κάποιος άλλος πριν πάει στρατό ο γιός μου θα σε παραδεχτώ (1).

 

β. Μερικοί recursive αλγόριθμοι είναι πολλαπλά γρηγορότεροι από αντίστοιχους με loops - π.χ. δες τις Mergesort και Quicksort - επίσης αν θές διάβασε και αυτό

 

Ε μαλλον θα ανήκουν στο 0.01 % .

 

(1). Δεν εχω παντρευτεί ακόμα. Βάλε καμια 30 χρονάκια δηλαδη.

[pietro]

activation record ti einai ?

[bandito]

activation record ti einai ?

 

 

activation record - (Or "data frame", "stack frame") A data structure containing the variables belonging to one particular scope (e.g. a procedure body), as well as links to other activation records.

 

Activation records are usually created (on the stack) on entry to a block and destroyed on exit. If a procedure or function may be returned as a result, stored in a variable and used in an outer scope then its activation record must be stored in a heap so that its variables still exist when it is used. Variables in the current scope are accessed via the frame pointer which points to the current activation record. Variables in an outer scope are accessed by following chains of links between activation records. There are two kinds of link - the static link and the dynamic link.

 

ΑΛΛΑ:

Αν φτιάξω resurse ΔΕΝ ΘΑ ΒΑΛΩ παπαδες μεσα.

Θα τα κάνω ολα static.

Βασικά δηλαδη, δεν έχει καμια διαφορά απο το loop αν τα κάνεις ολα static. Θυμηθήτε οτι "τελικα" ( κάτω, κάτω δηλαδη, στον κώδικα μηχανής ντε), δεν υπάρχουν loop recurse κτλ. Μερικα ταπεινα branches μονο.

[pietro]

Dhladh an katalava kala exoume ton frame pointer o opoios deixnei sto activation record ths function pou vriskomaste... to activation record apo thn alh einai mia stack h opoia exei oles tis dieu8hnseis mnhmhs twn metavlhtwn n,result,i?

[alkisg]

Κάθε φορά που καλείται μια συνάρτηση αποθηκεύονται στην στοίβα η τιμή του καταχωρητή εντολών, οι παράμετροι της συνάρτησης και πιθανώς κάποιοι καταχωρητές που χρησιμοποιεί η συνάρτηση. Πες δηλαδή από 8 - 16 bytes + sizeof(οι παραμέτροι σου). Όταν όμως οι παράμετροί σου είναι με αναφορά, τότε για κάθε μία να λογαριάζεις 4 bytes, όχι το μέγεθός της, γιατί περνιέται δείκτης.

 

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

 

Το μέγιστο μέγεθος της στοίβας στα περισσότερα λειτουργικά δηλώνεται στατικά, κατά την μεταγλώττιση του προγράμματος. Αν εσύ δηλώσεις 10 Mb στοίβα "απλά επειδή μπορεί να την χρειαστείς", τότε το πρόγραμμά σου δεν είναι αποδοτικό σε μηχανήματα με λίγη RAM. Αν πάλι δηλώσεις μικρή στοίβα και χρησιμοποιείς αναδρομή, τότε μπορεί να ξεμείνεις και το πρόγραμμά σου να διακοπεί με stack overflow.

 

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

 

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

 

@bandito: και στον κώδικα μηχανής υπάρχει διαφορά, δηλαδή εμφωλευμένες CALL = αναδρομή, πολλές JUMP = loop. Οι CALL γενικά έχουν πολύ μεγαλύτερο χρόνο εκτέλεσης από τις JUMP.

[bandito]

Κάθε φορά που καλείται μια συνάρτηση αποθηκεύονται στην στοίβα η τιμή του καταχωρητή εντολών' date=' οι παράμετροι της συνάρτησης και πιθανώς κάποιοι καταχωρητές που χρησιμοποιεί η συνάρτηση. Πες δηλαδή από 8 - 16 bytes + sizeof(οι παραμέτροι σου). Όταν όμως οι παράμετροί σου είναι με αναφορά, τότε για κάθε μία να λογαριάζεις 4 bytes, όχι το μέγεθός της, γιατί περνιέται δείκτης.

[/quote']

 

Και αν ειναι static, μην υπολογίσεις τίποτα.

Επιπλέον αν είναι έξυπνος o compiler, ευκολες αναδρομες τις κάνει loop.

 

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

 

Συνήθως όταν κάνεις μεγάλες αναδρομές, ειδικά σε δέντρα και άλλες παρόμοιες δομές, δεν θες να υπολογίσεις κατεβατά. Βάζεις το storage σου static και εισαι άρχοντας.

 

Το μέγιστο μέγεθος της στοίβας στα περισσότερα λειτουργικά δηλώνεται στατικά, κατά την μεταγλώττιση του προγράμματος. Αν εσύ δηλώσεις 10 Mb στοίβα "απλά επειδή μπορεί να την χρειαστείς", τότε το πρόγραμμά σου δεν είναι αποδοτικό σε μηχανήματα με λίγη RAM. Αν πάλι δηλώσεις μικρή στοίβα και χρησιμοποιείς αναδρομή, τότε μπορεί να ξεμείνεις και το πρόγραμμά σου να διακοπεί με stack overflow.

 

Δεν διαφωνώ. Όσο μικρότερο , τόσο καλύτερο. Όσο πιο γρήγορο, τόσο καλύτερο. Αμφιβάλλω δεν , για το ποιοι σκεφτονται την μνήμη πια, αφού για να τρέξεις hello world, στην visual basic θες 5-6 MB. Βέβαια στην περίπτωση smaller, faster μπορω να εκφράσω για όλα αντιρρήσεις, όπως γιατι loop για γνωστα μεγέθη , γιατι function calls (inline), γιατι math functions, κτλ

 

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

 

Τα overhead αυτο το κερδίζεις με πολλούς τρόπους σε συγκεκριμένους αλγόριθμους. Χάνεις μερικά push, pop, κερδίζες πολλα if, if not, why not, yes but κτλ. Επίσης, πραγματικά ειναι απλουστευμένα. Αν το ψάξεις υπάρχουν πολλοί τρόποι με αναδρομικούς αλγόριθμους , και να τους τρέξεις, και γρήγοροι να ειναι , και να μην δεσμευουν στοίβα. Σκέψου, οτι εναν recursive αλγόριθμο τον κάνεις ευκολα fork, το loop ούτε για πλάκα.

Τωρα που έρχονται τα διπλά , τριπλά, τετραπλά cores, η παράλληλη επεξεργασία θα έχει νόημα.

 

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

 

Ναι ε; Συγγνώμη αλλα γενικεύεις, λές και έχεις δουλέψει, σε όλα τα projects του κόσμου, και μιλάς απο πείρα. Εγώ τουλάχιστον, για να διατυπώσω μια θεωρία για το ποια ειναι η καλυτερη λύση σε όλα τα προβλήματα σε όλο τον κόσμο , θα περίμενα να βάλω καμια 30αριά χρόνια εμπειρίας στην πλάτη μου. Δεν θέλω να ξεκινήσω flame, αλλά έχω μια έμφυτη αποστροφή προς τις αυθεντίες, είτε αυτό που λες ειναι δικό σου, είτε ειναι γραμμένο κάπου και απλώς το μεταφέρεις.

 

The bottom line , ο καθείς στο είδος του και ο λουμίδης στους καφέδες.

 

@bandito: και στον κώδικα μηχανής υπάρχει διαφορά, δηλαδή εμφωλευμένες CALL = αναδρομή, πολλές JUMP = loop. Οι CALL γενικά έχουν πολύ μεγαλύτερο χρόνο εκτέλεσης από τις JUMP.

 

Αν ειναι ευκολη η αναδρομή στο δευτερο τριτο pass ο compiler το ψιλιάζεται και κανει το call , jump. Αλλα οπως είπα, τα γλυτώνεις απο τα if κτλ. Γενικά δεν διαφωνούμε, τα loops ειναι κατα κανόνα πιο γρήγορα. Αλλα αυτό δεν σημαίνει οτι ειναι ΠΑΝΤΑ πιο γρήγορα.

[nodreams.ct]

Aν ο compiler κάνει loop τις αναδρομές μαγκιά του,όμως δεν θα προσεύχομαι να έχω καλό compiler, θα το κάνω μόνος μου.

 

Γενικά συμφωνώ με το παιδί από πάνω για το footprint των αναδρομών. Και καλά για μικρές αναδρομές αλλά όσο περισσότερα function calls + local vars έχεις τόσο μεγαλώνει το πρόβλημα.

 

Πάντα έχεις το trade off: αν δεν σε νοιάζει η μνήμη και η ταχύτητα, αν έχεις λίγες αναδρομές, αν θες να κάνεις fork κτλ κάνεις την αναδρομή που έιναι πιο όμορφη, αν κάτι είναι time critical το γράφεις αναλυτικά.

 

Εγώ τον quicksort πάντως θα τον γράψω με stack, μια χαρά κατανοητός κώδικας μου φαίνεται.

 

αυτό δεν σημαίνει οτι ειναι ΠΑΝΤΑ πιο γρήγορα

 

For the argument's sake παράδειγμα γρηγορότερης αναδρομής!

[alkisg]

@bandito: Αγαπητέ το topic λέει "recursion h loop?" και όχι "bandito vs alkisg" . Τους διαξιφισμούς προσπαθώ να τους αποφύγω όσο μπορώ ακόμα και στην προσωπική μου ζωή, πόσο μάλλον στα fora... Κι εμένα μου την δίνουν οι αυθεντίες, πιστεύω όμως ότι έχω το δικαίωμα να καταθέτω την γνώμη μου χωρίς να "μου την λένε" άτομα που ούτε με ξέρουν, ούτε τα έθιξα... Το προγραμματιστικό μου background στο στέλνω σε pm, δεν νομίζω ότι σε κάθε post θα πρέπει να επισυνάπτω και CV. Αν θεωρείς ότι υπάρχει κάποιος λόγος προσωπικής αντιπαράθεσης στείλε μου email, στο insomnia μπαίνω λίγα λεπτά την μέρα για διάλειμμα από τον προγραμματισμό και όχι για εκτόνωση... Αν είχα αυτήν την ανάγκη θα πήγαινα στο γήπεδο. Παρακαλώ λοιπόν να ηρεμήσουν οι τόνοι και οι χαρακτηρισμοί του τύπου "καθείς στο είδος του και ο λουμίδης στους καφέδες" να σταματήσουν εδώ.

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

 

Πίσω στο topic.

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

 

2) Δεν έχω δει ακόμα κάποιον compiler που μπορεί να κάνει optimize τις αναδρομές σε loops (εκτός κι αν εννοείς την ειδική περίπτωση αναδρομικών συναρτήσεων που μπορεί να εφαρμοστεί Tail Recursion, δες http://en.wikipedia.org/wiki/Tail_recursion). Αν μπορείς γράψε κάποιο παράδειγμα με συγκεκριμένο compiler, πηγαίο πρόγραμμα καθώς και το αντίστοιχο πρόγραμμα σε assembly (π.χ. gcc -S mysource.c).

 

3) Τι εννοείς με το "όταν κάνεις μεγάλες αναδρομές βάζεις το storage σου static"; Αν δηλώσω ένα δέντρο static τότε πώς θα το αρχικοποιήσω, πώς θα το προσπελάσουν οι άλλες συναρτήσεις (π.χ. διάβασμα/αποθήκευση σε αρχείο κτλ);

 

4) "κερδίζεις πολλά if, if not, why not κτλ": Οι for/while/do σε assembly υλοποιούνται με compare και μετά (πιθανώς) jump. Η if σε assembly υλοποιείται με compare και μετά (πιθανώς) jump. Η κλήση συνάρτησης με call. Επομένως σε loops έχουμε (cmp/πιθανό jmp) και σε αναδρομές (call/cmp/πιθανό jmp). Δεν έχω υπόψη μου κάποια περίπτωση που η αναδρομή να είναι το ίδιο ή πιο γρήγορη από loop.

 

5) "έναν recursive αλγόριθμο τον κάνεις εύκολα fork, το loop ούτε για πλάκα": Τι εννοείς; Όταν κάνεις fork δημιουργείται αντίγραφο των data και stack segment, επομένως σε κάθε περίπτωση οι μεταβλητές (είτε του loop είτε της αναδρομής) είναι διαφορετικές για κάθε αντίγραφο της διεργασίας. Μήπως εννοείς threads, στα οποία το data segment είναι κοινό;

 

6) "Αλλά αυτό δεν σημαίνει ότι είναι πάντα πιο γρήγορα": η γνώμη μου είναι ότι τα loop είναι ΠΑΝΤΑ πιο γρήγορα, τουλάχιστον σε όσα είδη αρχιτεκτονικών γνωρίζω, όπου η CALL είναι πολύ πιο αργή από τις JMP. Αν μπορείς δώσε έστω και ένα παράδειγμα όπου η αναδρομή είναι γρηγορότερη από το loop.

 

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

 

Υ.Γ. #1 έχει αποδειχτεί ότι ΠΑΝΤΑ ένας αναδρομικός αλγόριθμος μπορεί να μετατραπεί σε επαναληπτικό, όμως δεν είναι πάντα εύκολο σε έναν προγραμματιστή να τον συντάξει (και δεν είναι πάντα κατανοητός αφού συνταχθεί)...

Υ.Γ. #2 υπάρχουν περιπτώσεις όπου συνίσταται (από βιβλία) να ΑΠΟΦΕΥΓΕΤΑΙ η αναδρομή, π.χ. στην ακολουθία fibonacci, αφού χρειάζονται εκατομμύρια αναδρομικές κλήσεις για να υπολογιστεί η fib(40)...

 

Φιλικά,

Άλκης