αναδρομη

[albNik]

Υπάρχει μια μέθοδος που λέγεται memoization.  Η ιδέα είναι να cache-αρεις τις ήδη υπολογισμένες τιμές ώστε να μην τις ξανα υπολογίσεις.  Εκεί χρειάζεται state.

int Fibonnacci(int n)
{
  if(this.FibArray[n]!=-1)
     return this.FibArray[n];
  else 
     this.FibArray[n]=Fibonnacci(n-1)+Fibonnacci(n-2);
  return FibArray[n];
}

 

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

[solarpower]

Ουσιαστικά όμως albNik,, δεν χρειάζεται η αναδρομή, αφού κρατάς πίνακα!

 

[albNik]

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

Ουσιαστικά όμως albNik,, δεν χρειάζεται η αναδρομή, αφού κρατάς πίνακα!

υπάρχουν προβλήματα που λύνονται ευκολότερα με αναδρομή. 

p.x. f(a) =f(a-3)+2*f(a-4);  

Ο μη ανάδρομηκος τύπος μπορεί να είναι πολύ περίπλοκος. 
Το προβλημα στην αναδρομή είναι ότι για να υπολογίσεις το f(100) θα χρειαστεί να υπολογίσεις πολλές φορές που.χ. το f(50). Με το memoization το λύνεις.

 

[defacer]

Also, packing problem. Φυσικά όλα αυτά μπορούν να γίνουν και με iteration αλλά εκεί το πρόβλημα είναι ακριβώς ότι γίνεται πιο δυσνόητος ο αλγόριθμος επειδή πρέπει να κρατάς manual stack.

[paparovic]

@albNik Δεν είναι απαραίτητο το state για να ένα memoize function. Μπορείς να το υλοποιήσεις σαν pure function.

Δες αυτό για παράδειγμα: https://medium.com/front-end-hacking/today-i-learned-memoization-with-pure-functions-in-es6-33a4765518b5

[albNik]

12 ώρες πριν, paparovic είπε

@albNik Δεν είναι απαραίτητο το state για να ένα memoize function. Μπορείς να το υλοποιήσεις σαν pure function.

Δες αυτό για παράδειγμα: https://medium.com/front-end-hacking/today-i-learned-memoization-with-pure-functions-in-es6-33a4765518b5

Έχω την εντύπωση ότι αυτό που έκανε δεν παίζει με ανδρομικές συναρτήσεις. Η εσωτερικές κλήσεις της fn (όταν είναι αναδρομική) δεν έχουν πρόσβαση στην cache. Άρα δεν μπορούν να την κάνουν update. 

αν η pureAdd ήταν αναδρομική θα είχε επαναληπτικούς υπολογισμούς  

let pureAdd = (x,y) => { pureAdd(x/2,y) + pureAdd(x/2,y) };

 

Οι παρακάτω είναι οι ενδεδειγμένοι τρόποι σε F#, Haskell

https://wj32.org/wp/2016/01/13/f-code-memoize-a-recursive-function/

https://stackoverflow.com/questions/9410330/memoization-with-recursion

Επεξ/σία 22 Ιουνίου 2018 από albNik