How recursion works?
Photo by Mario Mesaglio
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 case3 return4 f(n - 1)5 print(n)67f(4)89# this is how the recursion works10# f(4):11# 4 is printed12# f(3):13# 3 is printed14# f(2):15# 2 is printed16# f(1):17# 1 is printed18# f(0): # base case19# return20# 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}1718def printChildren(tree):19 if not tree['children']: # base case20 return21 for child in tree['children']:22 printChildren(child)23 print(child['name'])2425printChildren(tree)2627# this is how the result will be printed28# printChildren('Katie'):29# printChildren('Pam'):30# preintChildren('Tess'):31# return32# return33# printChildren('Angela'):34# printChildren('Jim'):35# return36# printChildren('Diane'):37# printChildren('John'):38# return39# return40# return4142# the children will be printed in the following order43# this is in order of the base case we reach first, as mentioned in the example above44# Tess, Pam, Jim, John, Diane, Angela