Αναδρομή στην Python

Στον προγραμματισμό υπάρχει η έννοια της αναδρομής - όταν μια συνάρτηση καλεί τον εαυτό της.

Παράδειγμα . Απλή αναδρομή με μετρητή

Ας εμφανίσουμε χρησιμοποιώντας αναδρομή αριθμούς από 1 έως 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # εδώ η συνάρτηση καλεί τον εαυτό της
		
	func()

Ας συζητήσουμε πώς λειτουργεί αυτός ο κώδικας.

Έχουμε μια καθολική μεταβλητή i και μια συνάρτηση func, μέσα στην οποία εμφανίζεται στην κονσόλα το περιεχόμενο της μεταβλητής i, και στη συνέχεια προστίθεται σε αυτήν μια μονάδα.

Εάν η μεταβλητή μας i είναι μικρότερη ή ίση με 10, τότε η συνάρτηση καλείται ξανά. Εφόσον η μεταβλητή i - είναι καθολική, τότε σε κάθε νέα κλήση της συνάρτησης σε αυτήν θα υπάρχει η τιμή της μεταβλητής i που ορίστηκε στην προηγούμενη κλήση.

Θα συμβεί ότι η συνάρτηση θα καλεί τον εαυτό της μέχρι η i να γίνει μεγαλύτερη από 10.

Λάβετε υπόψη ότι στην περίπτωσή μας δεν μπορεί η συνάρτηση να εκτελεστεί χωρίς if - εάν γίνει αυτό, θα προκύψει άπειρη κλήση συναρτήσεων.

Παράδειγμα . Αναδρομή για εμφάνιση στοιχείων εμφωλευμένων λιστών

Οι αναδρομές χρησιμοποιούνται συχνότερα για την επανάληψη λιστών διαφορετικού βαθμού εμφώλευσης. Ας υποθέσουμε ότι έχουμε την ακόλουθη λίστα:

lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]

Ας δημιουργήσουμε μια συνάρτηση που θα την επαναλάβει. Σε αυτήν πρώτα πρέπει να ορίσουμε μια συνθήκη, ώστε το στοιχείο, που είναι πρωτόγονο, δηλαδή απλώς ένας αριθμός που εξάγεται από τη λίστα, να εμφανίζεται στην κονσόλα. Και εάν το στοιχείο είναι ένα σύνθετο αντικείμενο, για παράδειγμα, μια εμφωλευμένη λίστα, τότε ας καλέσει σε αυτήν την περίπτωση η συνάρτηση τον εαυτό της, δηλαδή θα συμβεί αναδρομή. Για τον έλεγχο του τύπου του στοιχείου θα χρησιμοποιήσουμε τη συνάρτηση isinstance. Μόνο για το παράδειγμά μας στην πρώτη παράμετρο της isinstance θα γράψουμε el, και στη δεύτερη - τον τύπο list:

def func(lst):
	for el in lst:
		if isinstance(el, list):
			func(el)
		else:
			print(el)

Καλώντας τη συνάρτηση θα εμφανιστεί μια σειρά από όλους τους αριθμούς από την εμφωλευμένη λίστα:

func(lst) # θα εμφανίσει 1, 2, ... 8, 9

Παράδειγμα . Αναδρομή για πράξεις με στοιχεία εμφωλευμένων λιστών

Οι αναδρομές μπορούν να εφαρμοστούν και για διάφορες πράξεις με στοιχεία εμφωλευμένων λιστών. Ας υποθέσουμε ότι έχουμε την ακόλουθη λίστα:

lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]

Ας πάρουμε το άθροισμα όλων των στοιχείων της. Για αυτό στη συνάρτηση θα δηλώσουμε μια μεταβλητή res, στην οποία θα συσσωρεύεται το άθροισμα των αριθμών. Στη συνθήκη θα γράψουμε ότι εάν το στοιχείο είναι ένα σύνθετο αντικείμενο, τότε περνάει στην παράμετρο της συνάρτησης func και προστίθεται στο άθροισμα. Αυτό σημαίνει ότι το στοιχείο θα βρίσκεται σε αναδρομή μέχρι να γίνει πρωτόγονο. Και σε αυτήν την περίπτωση απλά θα προστεθεί στο άθροισμα, που είναι γραμμένο στην res:

def func(lst):
	res = 0
	for el in lst:
		if isinstance(el, list):
			res += func(el)
		else:
			res += el
	return res

Ας καλέσουμε τη συνάρτηση και ας εμφανίσουμε το αποτέλεσμά της στην κονσόλα:

print(func(lst)) # θα εμφανίσει 45

Παράδειγμα . Αναδρομή για συσσώρευση σε λίστα

Με τη βοήθεια αναδρομής μπορούμε να αναπτύξουμε εμφωλευμένες λίστες σε μια μονοδιάστατη λίστα. Ας υποθέσουμε ότι έχουμε την ακόλουθη λίστα:

lst = [1, [2, 3], [[4, 5], [6, 7, 8, [9]]]]

Ας γράψουμε στη συνάρτηση μια κενή λίστα res, στην οποία θα συσσωρεύονται στοιχεία της αρχικής λίστας. Στη συνέχεια θα εκτελέσουμε έναν βρόχο και θα ορίσουμε μια συνθήκη - εάν το στοιχείο είναι μια λίστα, τότε περνάει στη μέθοδο extend. Αυτή η μέθοδος συνδέει τα στοιχεία μιας λίστας στο τέλος μιας δεύτερης λίστας, δηλαδή τα στοιχεία της εμφωλευμένης λίστας θα μπουν στο τέλος της λίστας res:

def func(lst):
	res = []
	for el in lst:
		if isinstance(el, list):
			res.extend(func(el))
		else:
			res.append(el)
	return res
	
print(func(lst))

Το αποτέλεσμα του εκτελεσμένου κώδικα:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Πρακτικές ασκήσεις

Εμφανίστε όλα τα αριθμητικά στοιχεία ενός λεξικού αυθαίρετου βαθμού εμφώλευσης:

{
	'a': {
		'b': 1,
		'c': 2,
		'd': {
			'e': 3,
			'f': 4
		}
	},
	'j': {
		'h': 5,
		'k': 6,
	},
	'l': 7
}

Βρείτε το άθροισμα των στοιχείων του λεξικού από την προηγούμενη άσκηση.

Λάβετε μια λίστα πρωτόγονων στοιχείων του λεξικού από την προηγούμενη άσκηση.