This site runs best with JavaScript enabled.How recursion works?

How recursion works?


Simple examples of how recursion works

Recursion means “solving the problem via the solution of the smaller version of the same problem” or “defining a problem in terms of itself

example 1: printing 1 to n, given n > 1, n ∈ R

From the example below you can see that the numbers are printed from 1 to n instead of the intuitive n to 1.

This is because the printing is done after reaching the base case as show below.

1def f(n):
2 if n == 0: # base case
3 return
4 f(n - 1)
5 print(n)
6
7f(4)
8
9# this is how the recursion works
10# f(4):
11# 4 is printed
12# f(3):
13# 3 is printed
14# f(2):
15# 2 is printed
16# f(1):
17# 1 is printed
18# f(0): # base case
19# return
20# result will be 1, 2, 3, 4

example 2: Printing Children of a tree

It is super hard to do this iteratively, recursion saves the day here as shown below

1tree = {
2 'name': 'Katie',
3 'children': [
4 {
5 'name': 'Pam',
6 'children': [{ 'name': 'Tess', 'children': [] }]
7 },
8 {
9 'name': 'Angela',
10 'children': [
11 { 'name': 'Jim', 'children': [] },
12 { 'name': 'Diane', 'children': [{ 'name': 'John', 'children': [] }] }
13 ]
14 }
15 ]
16}
17
18def printChildren(tree):
19 if not tree['children']: # base case
20 return
21 for child in tree['children']:
22 printChildren(child)
23 print(child['name'])
24
25printChildren(tree)
26
27# this is how the result will be printed
28# printChildren('Katie'):
29# printChildren('Pam'):
30# preintChildren('Tess'):
31# return
32# return
33# printChildren('Angela'):
34# printChildren('Jim'):
35# return
36# printChildren('Diane'):
37# printChildren('John'):
38# return
39# return
40# return
41
42# the children will be printed in the following order
43# this is in order of the base case we reach first, as mentioned in the example above
44# Tess, Pam, Jim, John, Diane, Angela
Share article
James Chege

James Chege is a software developer in Nairobi