Αναδρομή

Το παρακάτω πρόβλημα μοιάζει να μπορεί να επιλυθεί με μια αναδρομική συνάρτηση:

Σε python το παραπάνω πρόβλημα γίνεται:

def f(x):
  if x>4:
    return(f(x-1)+x)
  else:
   return(x-f(x+1))

print(f(5)+f(6))

Ωστόσο όταν εκτελεστεί μας δίνει

RuntimeError: maximum recursion depth exceeded

Ο λόγος είναι ο εξής:

f(5)
return(f(4)+5)

f(4)
return(4-f(5))

f(5)
return(f(4)+5))

f(4)
return(4-f(5))

…

Οπότε κάποια στιγμή το πρόγραμμα φτάνει το μέγιστο βάθος αναδρομής και τερματίζει.

Το f(5) όμως μπορεί να υπολογιστεί αλγεβρικά με το παρακάτω σύστημα:

    \[\begin{cases} f(5) = f(4) + 5\\ f(4) = 4 - f(5) \end{cases}\]

Με πρόσθεση κατά μέλη έχουμε:

    \begin{eqnarray*} f(5)+f(4) &=& f(4) + 5 + 4 - f(5)\\ 2f(5) &=& 9\\ f(5) &=& 4.5 \end{eqnarray*}

Επίσης, f(6) = f(5) + 6 = 4.5 + 6 = 10.5.
Τέλος,

    \[f(5)+f(6) = 4.5 + 10.5 = 15\]

Το ίδιο αποτέλεσμα το έχουμε με το παρακάτω πρόγραμμα:

def f(x):
  if x == 5:
    return(4.5)
  elif x>4:
    return(f(x-1)+x)
  else:
    return(x-f(x+1))

print(f(5)+f(6))

Που εκτυπώνει:

15.0

Αφήστε μια απάντηση