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