CodeX
Published in

CodeX

Notes on recursion

This blog aims to simplify and visualize recursion concepts and its working

Photo by Mika Baumeister on Unsplash

Recursion is a programming concept that solves a complex problem by breaking it down into smaller sub problems.

A function that calls itself when it runs is a recursive function. For example, in Linux systems we use the command “ls -R” which tells the system to display all contents of the directory recursively or go into each folder and in turn subfloders and print the contents.

Stack overflow problem

The main drawback of recursive functions is the stack overflow problem.

When a Python program runs, the variables (address in the stack the variable points to or the reference) are loaded into the stack memory alongwith the return addresses of the function calls. The stack memory is however static, which means we can make a limited number of function calls. Also, stack is temporary since once the Python interpreter has executed the function call and returns to the next line the address is popped out of the stack. This blog explains memory management in Python in more details.

Since recursive functions call themselves, the return address of the next line of code gets stored in the stack the first time the function calls itself. Subsequently as the function keeps calling itself, the return addresses get stored in the stack and this can result in a stack overflow when the stack has no more space to store another address due to exhaustion of the stack memory.

Iteration, Recursion, Dynamic Programming

Coding a recursive solution involves the following :

  1. Identify base case : A base case refers to a stopping condition for the code so that once the base case is satisfied, the Python interpreter pops out the return addresses

2. Identify recursive case : The cases when the function needs to call itself or a recurrence relation that will call the function to solve a smaller similar sub problem than the original complex problem (divide and conquer approach)

3. Get closer and closer to the base case : As we go through recursive cases, at some point we should reach base case

def fibonacci(n):

if n <= 1: return n # base case

return fibonacci(n-1) + fibonacci(n-2) # recursive case

The function fibonacci is a recursive function where the first line is the base case; once we calculate fibonacci(1) the Python interpreter returns back n or 1 for this case. For any n > 1, the recursive case is satisfied and fibonacci gets called.

Recursion vs iteration :

While recursion keeps the code simple following the DRY (Don’t Reapeat Yourself) principle it also has a large memory footprint (a large callstack); so iteration might be useful for cases when we know how many iterations we want to go through.

Recursion is useful when we dont know the number of iterations and deal with data structures like trees, and linked lists. The process of traversing all the nodes of a binary tree is very simple using depth first search.

Let’s analyse the stack and the time taken for recursion for coding the Fibonacci series.

import inspect
import time
num_calls_list = []def fibonacci(n):
num_calls = 0

if n <= 1: return n

num_calls_list.append(len(inspect.stack())) # Return a list of the frames pushed onto stack for executing the current line of code


return fibonacci(n-1) + fibonacci(n-2)

We use inspect.stack() to view the Python call stack. We get back a named tuple as such

FrameInfo(frame, filename, lineno, function, code_context, index)

num_calls_list stores the len(inspect.stack()) at each recursive call. For n = 2 we get len(num_calls_list), num_calls_list :

1 [29]
  • 1 call to the function recursion, and 29 represents the number of stack calls from the function recursion till the final stack calls to the libraries used (since this is run on Anaconda we get the Anaconda frames added onto our stack too).

Printing the first element of the list returned by inspect.stack()

FrameInfo(frame=<frame at 0x0000027E131DECF0, file '<ipython-input-12-89cd151ff95a>', line 6, code fibonacci>, filename='<ipython-input-12-89cd151ff95a>', lineno=5, function='fibonacci', code_context=['    for ind, i in enumerate(inspect.stack()):\n'], index=0)

The first field frame has the frame information such as the address, filename that contains it,calling function <frame at 0x0000027E131DECF0, file ‘<ipython-input-12–89cd151ff95a>’, line 6, code fibonacci> ; the filename has the filename from where the function was called ‘<ipython-input-12–89cd151ff95a>'; the line called from in lineno; the function that is called ‘fibonacci’ in function; and the code context gives us the list of code lines at which this frame was inspected ; and index represents the index of the code context in the list.

For n = 3:

2 [29, 30]
  • For n = 3 we have :
Recursion tree for calculation of the fibonacci series for N = 3

1# fib(3) = fib(2) + fib(1) => fib(2) + 1

2# fib(2) = fib(1) + fib(0) => 1 + 0

  • 2 function calls where the second function call has 30 addresses stacked in the stack space (1 extra than the first owing to the recursive function call for calculating the fibonacci value of 2)

Similarly, for n = 5:

7 [29, 30, 31, 32, 31, 30, 31]

For n = 8:

33 [29, 30, 31, 32, 33, 34, 35, 34, 33, 34, 32, 33, 34, 33, 31, 32, 33, 34, 33, 32, 33, 30, 31, 32, 33, 34, 33, 32, 33, 31, 32, 33, 32]

For n = 15:

986 [29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 41, 40, 41, 39, 40, 41, 40, 38, 39, 40, 41, 40, 39, 40, 37, 38, 39, 40, 41, 40, 39, 40, 38, 39, 40, 39, 36, 37, 38, 39, 40, 41, 40, 39, 40, 38, 39, 40, 39, 37, 38, 39, 40, 39, 38, 39, 35, 36, 37, 38, 39, 40, 41, 40, 39, 40, 38, 39, 40, 39, 37, 38, 39, 40, 39, 38, 39, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 34, 35, 36, 37, 38, 39, 40, 41, 40, 39, 40, 38, 39, 40, 39, 37, 38, 39, 40, 39, 38, 39, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 33, 34, 35, 36, 37, 38, 39, 40, 41, 40, 39, 40, 38, 39, 40, 39, 37, 38, 39, 40, 39, 38, 39, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 34, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 40, 39, 40, 38, 39, 40, 39, 37, 38, 39, 40, 39, 38, 39, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 34, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 33, 34, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 34, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 35, 36, 37, 38, 37, 36, 37, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 40, 39, 40, 38, 39, 40, 39, 37, 38, 39, 40, 39, 38, 39, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 34, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 33, 34, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 34, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 35, 36, 37, 38, 37, 36, 37, 32, 33, 34, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 34, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 35, 36, 37, 38, 37, 36, 37, 33, 34, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 35, 36, 37, 38, 37, 36, 37, 34, 35, 36, 37, 38, 37, 36, 37, 35, 36, 37, 36, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 40, 39, 40, 38, 39, 40, 39, 37, 38, 39, 40, 39, 38, 39, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 34, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 33, 34, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 34, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 35, 36, 37, 38, 37, 36, 37, 32, 33, 34, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 34, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 35, 36, 37, 38, 37, 36, 37, 33, 34, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 35, 36, 37, 38, 37, 36, 37, 34, 35, 36, 37, 38, 37, 36, 37, 35, 36, 37, 36, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 39, 38, 39, 37, 38, 39, 38, 36, 37, 38, 39, 38, 37, 38, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 34, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 35, 36, 37, 38, 37, 36, 37, 33, 34, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 35, 36, 37, 38, 37, 36, 37, 34, 35, 36, 37, 38, 37, 36, 37, 35, 36, 37, 36, 32, 33, 34, 35, 36, 37, 38, 39, 38, 37, 38, 36, 37, 38, 37, 35, 36, 37, 38, 37, 36, 37, 34, 35, 36, 37, 38, 37, 36, 37, 35, 36, 37, 36, 33, 34, 35, 36, 37, 38, 37, 36, 37, 35, 36, 37, 36, 34, 35, 36, 37, 36, 35, 36]

Summarizing..

We see an exponential rise in the time taken, total function calls, and the total stack space used as N increases. Hence, recursion deems to not be a very efficient solution if we know the input N could vary to a very large number.

An iterative solution on the other hand, would use no extra stack space and find the solution in linear time.

Dynamic programming would help save time by storing the already calculated fibonacci series of a number so that we don’t have to perform redundant calculations in each iteration.

The following approach is a more efficient solution for this problem instead of recursion.

def fibonacci(n):
fib, fib_list = 0 , [] # array to store the fibonacci values
for i in range(0,n):
if i <= 1 :
fib_list.append(i)
else:
fib_list.append(sum(fib_list))
fib_list = fib_list[1:] # Use a window to only store the nessecary fibonacci series values to calculate the next

return fib_list[-1]+fib_list[-2]

The time taken is nearly a constant as N increases. We can see for N= 150 also, we get almost the same time as N= 0.

Depth first search on binary trees

Coding a recursive folution for printing the preorder traversal of a binary tree (root -> left -> right) :

def get_node(node):

if node == None: # base case
return

num_calls_list.append(len(inspect.stack()))
node_list.append(node.data) # Append to node_list

#print('left', node.data)
a = get_node(node.left) # Traverse left node ## Recursive case

# print('right', node.data)
b = get_node(node.right) # Traverse right node ## Recursive case

return

This solution is very simple to understand :

  1. Base case : Return to the calling function if current node is None
  2. Recursive case : If node is not None find the left node until None is returned by the base case; after that find the right node till None is returned.

We get the following output:

'1-> 2-> 5-> 4-> 6'

The original tree :

tree1

We consider two more trees, tree2 and tree3 of depth 4 and 8 :

tree2
tree3

Printing the time taken and the stack space we get:

Though the code is very simple to understand, we see a rise in the time taken and the stack space used as the depth of the tree increases.

On the other hand, if we use an iterative solution :

def print_node(linked_list):
node = linked_list.head
stack, preorder_traversal = [], [] # stack to store the previous node to pop ; preorder_traversal stores the order of nodes
while True:

if node != None: # keep finding the left node and store the root node in stack

preorder_traversal.append(node.data)

stack.append(node)
# print('Appending ', node.data, 'to stack ..', stack)

node = node.left

elif stack: # Once left node returns null, we pop the stack and find the right nodes

node = stack.pop()
node = node.right

else:
break

return preorder_traversal #print("-> ".join(preorder_traversal))

We get a constant time solution though the code is not as easy to understand as the recursive solution.

Thanks for reading!

Also, if there’s any suggestion to improve this article, please let me know!

Here is the link to the code for reference.

--

--

--

Everything connected with Tech & Code. Follow to join our 900K+ monthly readers

Recommended from Medium

15 Things you can do as Product Owner Improve Team Velocity

Customer Case Studies: How the Right Training Speeds Up Success in Digital and the Cloud

My First Open Source Contribution

AWS Certification Training Course for Solutions Architects

Cometd Resubscribe Multiple Dynamic channels on Connection Reopen.

Moving Platforms (part 2)

Breaking silos

Finally, InsureDAO testnet is out on Rinkeby testnet today, 6th August at 4:00 PM (UTC) !!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Aishani Basu

Aishani Basu

LinkedIn: https://www.linkedin.com/in/aishani-basu-83805b120/ | GitHub: https://github.com/aishani691

More from Medium

Why You Shouldn’t Learn Python

person writing code on a laptop with a book on python next to them

Dynamic Programming vs Greedy Technique

Compilation in C programming

A Never-Ending Debate Between Coding and Programming