Συναρτήσεις - Αναδρομική κλήση
Ασκήσεις κατανόησης
Άσκηση.
Γράψτε μία αναδρομική συνάρτηση sumN που θα δέχεται όρισμα ένα φυσικό αριθμό n και θα υπολογίζει το άθροισμα 1 + 2 + ... + n.
def sumN(n):
if n == 1:
return 1
else:
return n + sumN(n - 1)
print(sumN(4)) #prints 10
Άσκηση.
Γράψτε μία αναδρομική συνάρτηση multiply που θα δέχεται όρισμα δύο φυσικούς αριθμούς m και n και θα υπολογίζει το γινόμενο m * n.
def multiply(m, n):
if n == 1:
return m
else:
return m + multiply(m, n - 1)
print(multiply(5, 3)) #prints 15
Ασκήσεις εργαστηρίου
Άσκηση.
Γράψτε μία αναδρομική συνάρτηση sumInverseN που θα δέχεται όρισμα ένα φυσικό αριθμό n και θα υπολογίζει το άθροισμα 1 + 1/2 + ... + 1/n.
Άσκηση.
O αλγόριθμος του Ευκλείδη για την εύρεση του μέγιστου κοινού διαιρέτη βασίζεται στις παρακάτω σχέσεις:
gcd(a,0)=a
gcd (a,b) = gcd(b, a mod b)
Γράψτε μια αναδρομική συνάρτηση gcd που να δέχεται ως όρισμα δύο φυσικούς αριθμούς a και b και θα υπολογίζει το μέγιστο κοινό διαιρέτη τους.
Άσκηση.
Γράψτε μια αναδρομική συνάρτηση countDigits που να δέχεται ως όρισμα ένα φυσικό αριθμό n και να υπολογίζει το άθροισμα των ψηφίων του.
Άσκηση.
Γράψτε μια αναδρομική συνάρτηση recursiveSum που να υπολογίζει το άθροισμα των στοιχείων μιας λίστας ακεραίων.
Άλλες ασκήσεις
Άσκηση.
Γράψτε μια συνάρτηση που να παίρνει ως όρισμα ένα φυσικό αριθμό n και να επιστρέφει τη n-ιοστή γραμμή του τριγώνου του Pascal (τρίγωνο με τους διωνυμικούς συντελεστές).
[Υπόδειξη. Με εξαίρεση τις δύο πλευρές του τριγώνου όπου όλοι οι συντελεστές είναι 1, οι υπόλοιποι συντελεστές προκύπτουν αθροίζοντας τους δύο πάνω δεξιά και αριστερά όρους, όπως φαίνεται στην εικόνα.]
Άσκηση.
Το πρόβλημα των πύργων του Hanoi περιλαμβάνει 3 στήλες και N δίσκους διαφορετικών μεγεθών, όπως φαίνεται στην εικόνα παρακάτω. Σκοπός του προβλήματος είναι να μετακινήσουμε όλους τους δίσκους στην τελευταία στήλη χωρίς ποτέ όμως να βάλουμε έναν μεγαλύτερο δίσκο πάνω σε έναν μικρότερο.
Φτιάξτε ένα πρόγραμμα που να λύνει το πρόβλημα των πύργων του Hanoi.
[Υπόδειξη. Φτιάξτε μια αναδρομική συνάρτηση που να μετακινεί ένα αριθμό από δίσκους από μια αρχική στήλη σε μια τελική στήλη χρησιμοποιώντας την τρίτη στήλη ως βοηθητική.]