def factorialIter(n):
"""Assumes n is int > 0
returns n!"""
nfact = 1
while n > 1:
nfact = n*nfact
n -= 1
return nfact
Είναι όμως συχνά πιο απλό να σκεφτούμε ότι το παραγοντικό $(n+1)!$ μπορεί να υπολογιστεί άμεσα αν είναι γνωστό το $n!$, αφού $(n+1)! = (n+1)\cdot n!$. Αυτό ορίζει μία αναδρομική σχέση (το $n!$ υπολογίζεται αν γνωρίζουμε το $(n-1)!$, κλπ) και μας επιτρέπει να αναπτύξουμε μία επαγωγική μέθοδο. Η διαδικασία τερματίζεται αν γνωρίζουμε ότι $1!=1$ (βασική περίπτωση).
Για να γράψουμε έναν κώδικα ο οποίος θα εφαρμόζει την αναδρομική μέθοδο μπορούμε να γράψουμε μία συνάρτηση η οποία θα εφαρμόζει την αναδρομική σχέση για κάθε ακέραιο $n$.
def factorialRecur(n):
if n == 1:
return n
else:
return = n*factorialRecur(n-1)
factorialRecur χρησιμοποιεί την ίδια τη συνάρτηση (δηλαδή, αντίγραφο του εαυτού της) για να μπορέσει να εφαρμόσει την αναδρομική σχέση.
Επίσης, υπάρχει μία βασική περίπτωση (n==1) για την οποία οι διαδοχικές κλήσεις της συνάρτησης τερματίζονται, αλλιώς θα είχαμε διαδοχικές κλήσεις της συνάρτησης άπειρες φορές.
def fib(n):
if n == 0 or n == 1:
return 1
else:
return = fib(n-1) + fib(n-2)
Θα θέλαμε να μετρήσουμε πόσες κλήσεις γίνονται στη συνάρτηση fib (η οποία υπολογίζει με τον αναδρομικό αλγόριθμο έναν αριθμό Fibonacci) μέσω της αναδρομικής κλήσης της.
def fib(n):
global numFibCalls
numFibCalls += 1
if n == 0 or n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
def testFib(n):
global numFibCalls
numFibCalls = 0
print("Fibonacci number for",n,' = ',fib(n))
print("Function fib was called",numFibCalls,"times")
fib(n) είναι αρκετά μεγάλος. Γιατί συμβαίνει αυτό; Θα μπορούσαμε να γράψουμε διαφορετικά την fib(n) ώστε να χρειάζεται μικρότερος αριθμός κλήσεων;
def isPalindrome(L):
if len(L) <= 1:
return True
return L[0] == L[-1] and isPalindrome(L[1:-1])
L = [1, 2, [2, 3], [4], 6].
Γράψτε μια συνάρτηση η οποία κατασκευάζει μια «μονοδιάστατη» λίστα, αφαιρεί δηλαδή τυχόν εσωτερικές λίστες.
def flatten(L):
M = []
for item in L:
if isinstance(item, list):
for internalItem in item:
M.append(internalItem)
else:
M.append(item)
return M
isinstance(item,list) ελέγχει αν η μεταβλητή item είναι τύπου list. Δίνει αποτέλεσμα True/False.
Χρησιμοποιώντας αναδρομή μπορούμε να γράψουμε μία πιο κομψή μορφή του προηγουμένου προγράμματος.
Θα χρειαστούμε την μέθοδο M.extend(item) η οποία προσθέτει τα στοιχεία μίας λίστας item μετά το τελευταίο στοιχείο της λίστας L.
def flatten(L):
M = []
for item in L:
if isinstance(item, list):
M.extend(flatten(item))
else:
M.append(item)
return M
Η μορφή αυτή του προγράμματος περιλαμβάνει και την περίπτωση για την οποία μία λίστα περιέχει λίστες οι οποίες επίσης περιέχουν λίστες, π.χ., μπορεί να κάνει μονοδιάστατη την λίστα L = [1, 2, [2, [3,5]], [4], 6].