Θεωρητική ερώτηση

[kostaszabos]

Μπορούν όλες οι iterative μέθοδοι να μετατραπούν σε recursive μεθόδους? 

 

Εχω μιά iterative μέθοδο που παίρνει για παράμετρο ένα array από Strings και επιστρέψει ένα άλλο μικρότερο array  από String.. τα στοιχεία του input array τσεκάρονται ανά ζεύγη άν πληρούν κάποιες συνθηκες 

 

μπορεί αυτο να γίνει πιό απλά με recursive μέθοδο? 

εγώ νομίζω πώς θα έχουμε infinite loop γιατί δέν υπάρχει base condition.. 

 

αλλά και πάλι αν κάθε recursive μπορεί να μετατραπεί σε iterative και το αντίστροφο γιατί έχουμε infinite loop (Halting problem)?

[Predatorkill]

Μετα απο αυτο:

 

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

Δε νομιζω να σου απαντησει κανεις.

[White_Cat]

Καλησπέρα !

 

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

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

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

 Η εργασία των Church και Turing έχει αποδείξει με πολύ αυστηρά και τυπικά κριτήρια  ότι η μετάβαση από την αναδρομή στην επανάληψη και αντιστρόφως είναι πάντοτε δυνατή.

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

Ας πούμε ότι έχουμε αυτή την αναδρομική ρουτίνα στη C :

 

unsigned int fibonacci_recursive(unsigned int n)

{

    if (n == 0) 

    {

        return 0;

     } 

     if (n == 1) {

           return 1;

     }

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

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

unsigned int fibonacci(unsigned int n) {

unsigned int first = 0, second = 1, next, c;

for ( c = 0 ; c < n ; c++ )

   {

      if ( c <= 1 )

         next = c;

      else

      {

         next = first + second;

         first = second;

         second = next;

      }

}

return next;

}

Νομίζω ότι είναι αρκετά σαφές πώς απαλοίφει την αναδρομή η δεύτερη ρουτίνα. Θεωρεί δεδομένους εξ αρχής τους δύο πρώτους όρους της ακολουθίας που είναι το μηδέν και το ένα. Αυτούς τους πρώτους όρους τους τοποθετεί στις μεταβλητές first και second, ακόμα πριν μπει μέσα στον βρόγχο for. Κατόπιν χρησιμοποιεί τη μεταβλητή βρόγχου c για να μετράει τον αριθμό των επαναλήψεων μέχρι να φτάσουμε στο ζητούμενο n-οστό όρο Fibonacci. Σε κάθε επανάληψη αυτού του βρόγχου, αντί να δουλέύει με σωρό και δείκτες, απλά χρησιμοποιεί την ενδιάμεση μεταβλητή next, ώστε να κρατάει την προηγούμενη τιμή.

 

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

Επίσης ελπίζω να περάσατε καλά τα Κούλουμα,

Φιλικά, 

Ο Άσπρος Γάτος

[kostaszabos]

και γώ γάτα με πέταλα είμαι.. εννοια σου..

 

έχει αποδειχτεί απο το 1960... 

[bromiaris]

και γώ γάτα με πέταλα είμαι.. εννοια σου..

 

έχει αποδειχτεί απο το 1960... 

 

καβάλα στο καλάμι τον κόσμο γύρισα..

[defacer]

1. Ναι πάντα μπορεί να μετατραπεί (τουλάχιστον θεωρητικά), αυτό αποδεικνύεται σχετικά εύκολα ακόμα και διαισθητικά:

• Μια Τuring complete μηχανή μπορεί να εκτελέσει οποιοδήποτε υπολογισμό (πρόγραμμα)
• Ο ορισμός του Τuring completeness δεν περιλαμβάνει αναφορά ούτε σε iteration ούτε σε recursion -- ισοδύναμα, μπορείς να έχεις Τuring complete μηχανές που προγραμματίζονται μόνο με iterative ή μόνο με recursive γλωσσικά εργαλεία
• Αλλά ως Turing complete μηχανές είναι ισοδύναμες στο τι μπορούν να υπολογίσουν (αμφότερες "τα πάντα")
• Άρα πάντα είναι δυνατόν να μετατρέψεις το iteration σε ισοδύναμο recursion και αντίστροφα

2. Φυσικά και θα υπάρχει συνθήκη τερματισμού αναδρομής, είναι η ίδια συνθήκη που τερματίζει το loop ενδεχομένως λίγο προσαρμοσμένη.

 

3. Κλασικά δεν έχεις καταλάβει αυτά που κοπανάς δεξιά κι αριστερά, το halting problem δεν έχει απολύτως καμία σχέση μ' αυτά που λες.