Συζήτηση
Γεια χαρά, Επισκέπτης
Όνομα χρήστη: Κωδικός: Να με θυμάσαι

ΘΕΜΑ: Αναδρομική συνάρτηση

Αναδρομική συνάρτηση 6 Χρόνια 9 Μήνες πριν #4545

  • eternx
  • Το Άβαταρ του/της eternx
  • Αποσυνδεμένος
  • p_____
  • Δημοσιεύσεις: 1
Είχα μια απορία στον παρακάτω κώδικα.

def fact(n):
if n == 1:
return n
else:
return n * fact(n - 1)


Στην τελευταία γραμμή, το fact(n - 1) παύει να εκτελείται όταν φτάσει το 1; Είναι δηλαδή προκαθορισμένο όταν φτάσει το 1 να σταματάει;
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Αναδρομική συνάρτηση 6 Χρόνια 9 Μήνες πριν #4548

  • babaliaris1
  • Το Άβαταρ του/της babaliaris1
  • Αποσυνδεμένος
  • python
  • Δημοσιεύσεις: 445
  • Ληφθείσες Ευχαριστίες 75
eternx έγραψε:
Είχα μια απορία στον παρακάτω κώδικα.

def fact(n):
if n == 1:
return n
else:
return n * fact(n - 1)


Στην τελευταία γραμμή, το fact(n - 1) παύει να εκτελείται όταν φτάσει το 1; Είναι δηλαδή προκαθορισμένο όταν φτάσει το 1 να σταματάει;

Ναι, αφού εσύ το λες να σταματήσει όταν το n ισούται με 1.

Επίσης αν το n είναι μικρότερο του 1, τότε δεν θα συναντήσεις ποτέ το 1 και συνέχεια θα καλείς αναδρομικά την συνάρτηση (Infinity loop).

Πάρε για παράδειγμα για n = 3:

Κλήση 1: fact(3)

Είναι το n == 1; (Όχι είναι 3) άρα return 3 * fact(2)

Κλήση 2: fact(2)

Είναι το n == 1; (Όχι είναι 2) άρα return 2 * fact(1)

Κλήση 3: fact(1)
Είναι το n == 1; (Ναι) άρα return n

Επιστροφή από την κλήση 3 στην 2 (Η τρία επιστρέφει 1):
return 2 * fact(1) = return 2 * 1 = return 2

Επιστροφή από την κλήση 2 στην 1 (Η δύο επιστρέφει 2):
return 3 * fact(2) = 3 * 2 = return 6

Άρα τελικά το αποτέλεσμα είναι 6.
Τελευταία διόρθωση: 6 Χρόνια 9 Μήνες πριν από babaliaris1.
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Αναδρομική συνάρτηση 6 Χρόνια 9 Μήνες πριν #4549

  • Theo
  • Το Άβαταρ του/της Theo
  • Αποσυνδεμένος
  • pytho_
  • Δημοσιεύσεις: 249
  • Ληφθείσες Ευχαριστίες 70
Ένας τρόπος σκέψης που έχω δει και με έχει βοηθήσει να καταλάβω κάπως την αναδρομή είναι αυτός των layers.
Αν για παράδειγμα καλέσουμε την fact(8) αυτή θα καλέσει την fact(7) που θα τρέχει σε άλλο layer η 7 θα καλέσει την fact(6) που θα τρέχει σε άλλο layer
κλπ μέχρι και την fact(1) και όλες θα τρέχουν παράλληλα σε 7 layers και θα περιμένουν. Η fact(1) θα επιστρέψει όπως λέει η συνάρτηση η fact(2) θα περιμένει την fact(1) η fact(3) την fact(2) η fact(4) την fact(3) .... κλπ

Κάτι που πρέπει να γνωρίζουμε για το recursion είναι ότι ενώ σαν ιδέα μαθηματική είναι απλή από άποψη απόδοσης για τους υπολογιστές και σαν χρόνος και σαν μνήμη είναι καταστροφή και κάνει τη χρήση της απαγορευτική για κάθε είδους υπολογισμούς
Όσες φορές το έχω χρησιμοποιήσει αναγκάστηκα να το αλλάξω
Τελευταία διόρθωση: 6 Χρόνια 9 Μήνες πριν από Theo.
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Αναδρομική συνάρτηση 6 Χρόνια 8 Μήνες πριν #4553

  • pmav99
  • Το Άβαταρ του/της pmav99
  • Αποσυνδεμένος
  • Author
  • Δημοσιεύσεις: 684
  • Ληφθείσες Ευχαριστίες 111
Η απόδοση της recursion είναι κακή στην Python, όχι γενικά.
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Αναδρομική συνάρτηση 6 Χρόνια 8 Μήνες πριν #4558

  • Theo
  • Το Άβαταρ του/της Theo
  • Αποσυνδεμένος
  • pytho_
  • Δημοσιεύσεις: 249
  • Ληφθείσες Ευχαριστίες 70
Έχουμε όμως την lru_cache που δεν νομίζω ότι το έχει κάποια άλλη γλώσσα :woohoo:
ο fibonacci σε 3 εκδοχές
#Η standar αργή με lru όμως
@lru_cache(maxsize=None)
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
 
#O χαζός που προτείνει η python στην επίσημη σελίδα  :lol: 
def fibi(n):
    old, new = 0, 1
    if n == 0:
        return 0
    for i in range(n-1):
        old, new = new, old + new
    return new
 
#δυναμικά 
memo = {0:0, 1:1}
def fibm(n):
    if not n in memo:
        memo[n] = fibm(n-1) + fibm(n-2)
    return memo[n]
και οι χρόνοι άμα εκτελεστούν οι συναρτήσεις με όρισμα το 40 1000000 φορές
>>> t('fibi(40)', number=1000000, globals=globals())#χαζός
4.01949755542887
>>> t('fibm(40)', number=1000000, globals=globals())#dynamic programming
0.22513274835819175
>>> t('fib(40)', number=1000000, globals=globals())#lru
0.146481831745632
>>> 
Τελευταία διόρθωση: 6 Χρόνια 8 Μήνες πριν από Theo.
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Αναδρομική συνάρτηση 6 Χρόνια 8 Μήνες πριν #4563

  • pmav99
  • Το Άβαταρ του/της pmav99
  • Αποσυνδεμένος
  • Author
  • Δημοσιεύσεις: 684
  • Ληφθείσες Ευχαριστίες 111
To lru_cache είναι απλά μια συνάρτηση για memoization (δηλαδή για caching) και δεν έχει και τόσο σχέση με το αν θα χρησιμοποιήσεις αναδρομική συνάρτηση ή όχι.

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

Αναδρομική συνάρτηση 6 Χρόνια 8 Μήνες πριν #4585

  • myle
  • Το Άβαταρ του/της myle
  • Αποσυνδεμένος
  • Admin
  • Δημοσιεύσεις: 467
  • Ληφθείσες Ευχαριστίες 15
pmav99 έγραψε:
Η απόδοση της recursion είναι κακή στην Python, όχι γενικά.

stackoverflow.com/questions/13591970/doe...imize-tail-recursion

Ενώ γενικά, δεν χρειάζεται καν call stack:
en.wikipedia.org/wiki/Tail_call
«Αν υποθέσουμε ότι αυτό είναι δυνατό, (να μεταδώσουμε τη σοφία παντού) τότε ειλικρινά ο τρόπος ζωής των θεών θα περάσει στους ανθρώπους. Τα πάντα θα είναι γεμάτα...
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.
Συντονιστές: pmav99
Χρόνος δημιουργίας σελίδας: 0.382 δευτερόλεπτα

Μοιράσου το!

Powered by CoalaWeb

Λίστα Ταχυδρομείου