Recursion in Python

In programming, there is such a concept as recursion - when a function calls itself.

Example . Simple recursion with counter

Let's use recursion to derive numbers from 1 to 10:

i = 1

def func():
	global i
	print(i)
	i += 1
	
	if i <= 10:
		func() # here the function calls itself func()

Let's discuss how this code works.

We have a global variable i and a function func, inside which the contents of the variable i are printed to the console, and then one is added to it.

If our variable i is less than or equal to 10, then the function is called again. Since the variable i is global, then with each new call of the function it will contain the value of the variable i set in the previous call.

It turns out that the function will call itself until i becomes greater than 10.

Note that in our case, we cannot run the function without if - doing so would result in an infinite function call.

Example . Recursion for printing elements of nested lists

Most often, recursion is used to iterate over lists of varying degrees of nesting. Let's say we have the following list:

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

Let's create a function that will iterate over it. First, we need to set a condition in it so that an element that is a primitive, i.e. simply a number extracted from the list, is output to the console. And if the element is an object, for example, a nested list, then let the function call itself in this case, i.e. recursion will occur. To check the element type, we will use the isinstance function. Only for our example, in the first parameter isinstance we will write el, and in the second - the type list:

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

When the function is called, a series of all numbers from the nested list will be output:

func(lst) # 1, 2, ... 8, 9

Example . Recursion for operations with elements of nested lists

Recursions can also be used for various operations with elements of nested lists. Let us have the following list:

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

Let's get the sum of all its elements. To do this, we declare a variable res in the function, in which the sum of numbers will be accumulated. In the condition, we write that if the element is a complex object, then it gets into the parameter of the function func and is added to the sum. This means that the element will be in recursion until it becomes a primitive. And in this case, it will simply be added to the sum written in res:

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

Let's call the function and print its result to the console:

print(func(lst)) # 45

Example . Recursion for accumulation into a list

Using recursion, we can decompose nested lists into a single one-dimensional list. Let's say we have the following list:

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

Let's write an empty list res in the function, into which the elements of the original list will accumulate. Next, we'll start the loop and set the condition - if the element is a list, then it will go to the extend method. This method appends the elements of one list to the end of the second list, i.e. the elements of the nested list will go to the end of the res list:

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))

The result of the executed code:

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

Practical tasks

Print all numeric elements of a dictionary of arbitrary nesting level:

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

Find the sum of the elements of the dictionary from the previous problem.

Get the list of primitive elements of the dictionary from the previous problem.