αναδρομη

[ForThwWin]

γεια σας

θα ηθελα να ρωτησω κατι σχετικα με τη μεθοδο της αναδρομης

1)Μπορουν ολες οι συναρτησεις να γραφουν σε μια αναδρομικη μορφη;

2)Αν υποστηριζουν ολες οι γλωσσες προγραμματισμου την αναδρομη(γνωστης μονο σε C)

[mad-proffessor]

1)  Μπορείς να το απαντήσεις μόνος σου αν σκεφτείς τι είναι μια συνάρτηση, απο τι αποτελείται μια συνάρτηση και πότε/γιατί χρειάζομαι αναδρομή.

2) Αν μπορείς να δημιουργήσεις συνάρτηση στη γλώσσα τότε προφανώς το υποστηρίζει

[ForThwWin]

αν καταλαβα απο το 2 μ απαντησες κι το πρωτο ερωτημα

[albNik]

Στο 1 μάλλον ρωτάς αν πάντα οι βρόγχοι (for, while ) μπορούν να μετατραπούν σε αναδρομή.

Η απάντηση είναι Nαι.

[solarpower]

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

Που δεν έχουμε αναδρομή;

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

[defacer]

@solarpower δε μου ακούγονται καθόλου σωστά όπως τα λες. Ξεκινώντας από την πρώτη πρόταση, που θα έλεγα το ακριβώς αντίθετο (η αναδρομή είναι τεχνική και όχι language feature) μέχρι και την τελευταία (κάνε compile ένα πρόγραμμα σε C με αναδρομή και πέρνα το από disassembler, τώρα "έχει αναδρομή η assembly" ή όχι?).

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

Επεξ/σία 16 Ιουνίου 2018 από defacer

[solarpower]

Η αναδρομή είναι τεχνική;

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

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

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

Δες όμως τι λες. Ότι σε C εφαρμόζουμε το χαρακτηριστικό της αναδρομής (εσύ το θες ως τεχνική) και εξάγουμε τον Assembly κώδικα (που είναι ισοδύναμος με το πρόγραμμα στη C). Και τώρα θες να καταλήξεις ότι η τεχνική που γράφτηκε σε C πέρασε στην Assembly.  Όχι δεν πέρασε. Ο κώδικας από C μεταφράστηκε σε Assembly. Η όποια τεχνική καταναλώθηκε στην μετάφραση. Από τη στιγμή που παίρνουμε τον Assembly κώδικα, έχουμε μια μετάφραση ενός ισοδύναμου προγράμματος, με όποιο τρόπο και τεχνική επιλέχθηκε αυτόματα από τον μεταφραστή. Το αποτέλεσμα της αναδρομής μπορεί να φτιαχτεί με ισοδύναμο πρόγραμμα σε Assembly, αλλά αυτό που φτιάχνουμε θα είναι "ισοδύναμο"  και όχι τεχνική αναδρομής.
Με την ίδια έννοια ο προγραμματισμός με γεγονότα δεν είναι τεχνική της Assembly, αλλά σίγουρα ένα πρόγραμμα που τον χρησιμοποιεί μπορεί να δώσει το ισοδύναμο σε Assembly. Παραμένει όμως ότι η assembly δεν έχει γεγονότα. Βεβαίως μπορεί να φτιάξει κανείς πρόγραμμα που να χρησιμοποιεί γεγονότα όπως ορίζονται από εξωτερικές βιβλιοθήκες, και πάλι όμως αυτό δεν ορίζεται από την Assembly αλλά από ένα επίπεδο "οργάνωσης" πάνω από αυτήν.

 

[Ilias95]

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

Αλλά αν στην assembly έχεις ένα label που αντιστοιχίζεται σε ένα συγκεκριμένο block εντολών (aka συνάρτηση) και μέσα σε αυτό το block εντολών έχεις ένα call στο ίδιο function/label για ποιον λόγο ακριβώς δεν το θεωρείς αυτό αναδρομή; 

Μιλώντας πάντα για συμβολική αναπαράσταση της assembly όπου έχουμε ονόματα/ετικέτες.

Επεξ/σία 18 Ιουνίου 2018 από Ilias95

[kaliakman]

@solarpower

 

Όταν διδάχθηκες την αναδρομή την έμαθες με κάποια γλώσσα ή σου την εξήγησαν χωρίς να σου πουν συγκεκριμένη γλώσσα;

Από την απάντηση καταλαβαίνεις οτί δεν είναι χαρακτηριστηκό μιας γλώσσας αλλά τεχνική που οι γλώσσες την υποστηρίζουν. Ένα ακόμα παράδειγμα είναι ο πολλαπλασιασμός. Είναι feature μιας γλώσσας; Με την λογική σου ναι γιατί η γλώσσα έχει φροντίσει το σύμβολο '*' να σημαίνει πολλαπλασιασμός.

Επεξ/σία 18 Ιουνίου 2018 από kaliakman

[solarpower]

@Ilias95,

πάλι με το aka συνάρτηση, πάς στο ισοδύναμο. Όμως δεν υπάρχουν συναρτήσεις στην Assembly.

 

@Kaliakman

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

Ο πολλαπλασιασμός είναι ένα βαρύ πράγμα για να το λέμε τεχνική ή χαρακτηριστικό.  Διότι άλλο ο πολλαπλασιασμός δυο ακεραίων, άλλο ο πολλαπλασιασμών αριθμών χωρίς πρόσημο, άλλο ο πολλαπλασιασμο αριθμών κινητής υποδιαστολής...κ.ο.κ. Το δε * παίζει να είναι χαρακτηριστικό. Δες στη Lisp πως δίνεται!

 

[Ilias95]

3 ώρες πριν, solarpower είπε

@Ilias95,

πάλι με το aka συνάρτηση, πάς στο ισοδύναμο. Όμως δεν υπάρχουν συναρτήσεις στην Assembly.

Πώς θέλεις να τις ονομάσουμε; Routines;
Τα calling  conventions σε τι εξυπηρετούν;

Anyway, μην βγούμε και offtopic.

Επεξ/σία 18 Ιουνίου 2018 από Ilias95

[solarpower]

Οι τρόποι κλήσης συναρτήσεων είναι θέμα γλώσσας, γιατί απλά η συνάρτηση ορίζεται σε υψηλότερο επίπεδο από το επίπεδο της Assembly. Έχουμε άλλο επίπεδο "Αφαίρεσης". Ομοίως η αναδρομή είναι ένα επίπεδο αφαίρεσης που δεν παίζει σε επίπεδο assembly,  και μπορεί να επιδειχθεί ως τεχνική επίλυσης προβλημάτων. Άλλο η αναδρομή ως τεχνική και άλλο η γλώσσα με συναρτήσεις με χαρακτηριστικό αναδρομής. Μπορεί κανείς να προσομοιώσει την αναδρομή ως τεχνική με πίνακες και να πάρει το ίδιο αποτέλεσμα.

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

 

 

 

[albNik]

38 λεπτά πριν, solarpower είπε

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

Γιατί όχι;
Τι εμποδίζει την αναδρομική συνάρτηση να είναι member κάποιου object;

Calculator c = new Calculator();
int result = c.Fibonacci(5);

 

[defacer]

15 hours ago, solarpower said:

Όμως δεν υπάρχουν συναρτήσεις στην Assembly.

Ποια είναι η διαφορά ανάμεσα στο call_myself()...return και στο CALL...RET της assembly, ή στο GOSUB...RETURN της BASIC?

Η μοναδική διαφορά είναι ότι στην πρώτη περίπτωση ο compiler κανονίζει να γράψει function prolog/epilog αυτόματα, ανάλογα με το signature και τα calling conventions, ενώ στις άλλες δύο αν το χρειάζεσαι πρέπει να το κάνεις μόνος σου.

Καταλαβαίνω τι λες, "υποστηρίζει" με την έννοια του παρέχει language feature που υλοποιεί απευθείας την τεχνική, όπως θα λέγαμε ότι "η C δεν υποστηρίζει OOP" (μια δήλωση με την οποία επίσης θα διαφωνούσα ακριβώς με τον ίδιο τρόπο). Άλλο κλασικό παράδειγμα η υλοποίηση closure σε C++, πράγμα που μπορούσε να γίνει ανέκαθεν χειρωνακτικά και κάποια στιγμή πήρε προαγωγή σε language feature.

Προσωπικά πηγαίνω με τη θεώρηση όχι του language feature γιατί διαφορετικά μου φαίνεται πως είναι εύκολο να γίνει μπέρδεμα ανάμεσα στο concept (τεχνική) και την υλοποίηση (language feature), ίσον "αν δεν υπάρχει δυνατότητα για recursive function call τότε δεν υπάρχει recursion".

Επεξ/σία 19 Ιουνίου 2018 από defacer

[solarpower]

Τώρα συυμφωνώ όπως το θέτεις, concept vs feature. Και νομίζω ότι ο θεματοθέτης εδώ θέλει να βρει τις γλώσσες με το χαρακτηριστικό έτοιμο.

Ας δούμε το θέμα με τα αντικείμενα.

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

Μπορεί να υπάρχει χαρακτηριστικό αναδρομής σε μεθόδους ενός αντικειμένου, αλλά ποιος ο λόγος να υπάρχει; Ο  albNik έδωσε ένα παράδειγμα που απλά το OOP εδώ χρησιμοποιείται ως βιβλιοθήκη συναρτήσεων. Δεν υπάρχει λόγος να είναι σε αντικείμενο, εκτός αν δεν γίνεται αλλιώς, αν η γλώσσα δεν υποστηρίζει συναρτήσεις εκτός αντικειμένων.

Καμιά ιδέα με άλλη χρήση της αναδρομής;