DEV Community: Subhasree

Quick start to Recursion | Identify Use case | In Simple Words

Subhasree — Sun, 30 Oct 2022 12:15:34 +0000

Hey there! Hope you are doing well. In this article, I am going to cover

What is recursion,
How memory is allocated for recursion
When we should use recursion ( over iteration )
It’s limitations ( or when not to use )
Reference Articles.

What is Recursion?

So let’s start with a real world example. A simple yet exciting illustration is Googling Recursion. Noticed what happens?

It keeps asking you "Did you mean Recursion?" And even after clicking it, it continues to prompt the same question. Doesn’t it appear to be calling itself over and over again? Well, that is recursion in play.

In simple words, Recursion is the process where a function calls itself directly or indirectly.

def counting(no):

  print(no)
  counting(no+1)

When does recursion stop?

As you have already noticed, in the above example, the recursion goes infinitely. With this, our terminal will overflow with prints and the program’s call stack might crash with Stack overflow, where it will be no longer able to track any further function calls.

So how do we stop it? We use a simple base case from where the function returns with a terminal point and does not call itself any further.

def counting (no):
  if no==10:
    print("Recursion ends at 10")
  else:
    print(no)
    counting(no+1)

In the above code, when our recursion hits an input with no=10, it simply prints the statement and no longer calls itself again. Thus, we do not have any stack overflow this time.

Doesn’t it sound similar to iteration?

Well, it does. Like iteration (irrespective of ‘for’ or ‘while’ loop), in recursion also, we perform sub-tasks repetitively. So broadly speaking, we can implement every logic of recursion with iteration if we want and vice versa.

Then why recursion?

Even though it looks similar, recursion has certain advantages over iteration on the basis of readability of code.

Specially when we need to maintain a stack to keep track of processes we are calling so that they can be referenced again at later point of time. Unlike in iteration, recursion keeps a memory call stack implicitly for its execution.

How Recursion works?

As said, Recursion works with the help of Memory Call stack.

In other words, when any function gets called, some memory is allocated for storing its data so that it can be referenced when required. This memory does not get freed up until the function has returned its control or exited from the function’s reference.
Now when other functions get called successively, those calls get stacked in the memory as well, until its execution is completed one by one in LIFO (Last In First Out) sequence.

The same process takes place when recursion happens. All the function calls get stacked in the memory until they are executed. Once a function returns its control, the stack is popped and next function call in the stack is being executed.

Let’s analyse with a code snippet:

def counting(no):
    if no>5:
        return
    counting(no+1)
    print(no, end = " ")

counting(0)

The output of the code snippet will look like: 5 4 3 2 1 0

Why the output is in reverse order?

If we run in debug mode and watch the call stack, we will find something like:

Decoding Call stack:

As we can see, the call stack started with the function call at line no. 9 . This is the entry point of our recursive function and counting(0) gets pushed.
Post that, every time we were calling counting(no+1) , from line no. 6 , we have an entry of it in the call stack with the corresponding value. Print statement never gets executed since before that only Function invokes itself recursively.
Once we reach the base case that is, no>5 , we return from the function for the first time. Hence the last function call that got pushed with no=6 gets popped out of the stack.
Hereafter, popping from the call stack begins. Memory points the next function in the call stack and execute the remaining statements in the function which previously weren’t executed.
In this case, print(no) gets executed and 5 gets printed in the terminal.
Similarly, all successive functions get popped out of the call stack one by one in LIFO manner and the print statement is executed with the corresponding values of no .Hence 4 3 2 1 0 gets printed.

And that’s it.

When to use it?

From the above code examples, it can be seen that the same task of printing number is getting repeated as the function keeps calling itself with a different parameter.

In other words, we can find the use of recursion where

We have a definite subtask to be performed.
We want to repeat that subtask over and over again.
We need a stack to keep track of processes so that can be referenced later.

For example, to implement traversing trees, recursion would be a better choice.

When not to use it?

Even with this tempting advantage of recursion (who does not like readable code? 👀) , Recursion has certain disadvantages. As we have already seen, recursion requires more memory usage since it saves each function calls in the implicit stack. This can be a major overhead when a task is simpler. In those cases, iteration should be the better choice.

For example, to implement fibonacci series iteration would be a better option than recursion.

References:

Conclusion:

I hope this article helps you to get started with the basic concepts of Recursion.

In the upcoming articles, I am going to cover recursion in more depth like how it works internally, how each operation is handled in recursive functions, more advance example and its complexity with optimisation techniques like dynamic programming.

For such updates and articles on Data structure and algorithm, follow this page and keep supporting. Cheers! 🥂

Quick Start to Priority Queue and Heap | With Python

Subhasree — Sun, 24 Apr 2022 13:08:37 +0000

Priority Queue

Starting with Priority Queue, let’s first understand what a simple queue is and how it is different from a Priority Queue.
Can think of a line where you had to stand, waiting for your turn to get your Pizza, or may be to get into a bus? That is a queue you are standing in. A simple queue, where the first person who joined it, will be the first one to leave it too. Hence, a FIFO (or First In First Out) linear data structure.

Now imagine, what if in that same queue, a celebrity joins in? Or may be the President of your country? Would that person be standing at the end of the queue now to wait for his turn? Well, in this circumstances, you might want them to go before you, despite the fact they joined last.

This is a priority queue where each data in the queue has a certain priority and the data with highest priority goes out first and then the second and so on.

Implementation

From the above example, it can be seen that a simple queue cannot be used to implement a priority queue, where each data is associated with some weight. So far, priority queue is just like an Abstract Data Type which has to be implemented separately to get the desired order.

Note: Priority queue only supports the data which can be compared with each other. That is, it should be possible to order the data from least to highest priority or highest to least priority.
A classic implementation of Priority Queue can be with Binary Heap.

Binary Heap

As the name suggests, in a binary heap, every node has at most two children. Sounds similar to Binary Tree? Well, Binary heap is a special kind of binary tree where the ordering of every nodes matter. In which way, let’s find those below:

Each Node has higher priority than its children’s. In the below diagram, the red coloured numbers represent the priorities of the nodes.

Every heap is a complete binary tree, meaning each level in the tree should have the maximum number of nodes, except the last level.

Insertion of new Node always happens from left to right and only in the last level (or new next level when the last level is complete). In case of violation of the Heap Property after insertion, swapping must takes place to satisfy it. For example, if we try to insert 4 to the above valid heap:

There are two types of Heaps:

Max Heap — In this, nodes are ordered from larger values in the top levels to smaller values in the lower levels.

Min Heap — In this, nodes are ordered from smaller values in top levels to larger values in lower levels.

The root node of a Heap always contains the element with highest priority or greatest value in case of Max heap or lowest value in case of Min heap, which is removed first when popped from the Heap.

Representations of Heap:

A Heap can be typically represented with an array.

The above Heap can be represented as :

Now some points to note from the array implementation:

Here we can clearly see that for each node at index i, the children nodes are at (2*i + 1, 2*i +2)
Parent of a node at index i is (i-1)//2
To distinguish between Leaf and internal nodes, we have : if n is the length of the array, then any node at index i is internal if 2*i+2 <= n. Else it is a leaf node.

Operations on Binary Heap

We can now implement Priority Queue requirements with the help of a Binary heap but in extreme rare occasions, we will need to write the entire implementation from scratch by ourselves. Since already lots of libraries in most of the programming languages offer pre-built Heaps , knowing how it works and how to use the implementations to get our desired output often suffice.

In this article, we will go through the Python 3 library, heapq, for Heap implementation and get an overview of what their major functions do.

Heapify:

Starting with Heapify, it is the process of creating a heap data structure from a binary tree. Both Min-Heap or a Max-Heap can be created with this process.

This process is also used internally to maintain the heap property after insertion or deletion of a node. Time complexity of the process is O(logn).

Heap Pop or Delete:

This is the process of popping out element from the Heap, in which always the root node gets deleted first.
The deletion starts with replacement of the last element with the root node to be deleted and then heapifying the last node in its correct index.

This process uses PercolateDown approach and the Time complexity is O(logn).

Heap push or Insertion:

This is the process of inserting new value into the Heap, which always happens at the last level, from left to right order. In case of violation of the Heap property, heapifying the tree may takes place and the process uses PercolateUp approach with a time complexity of O(logn).

A simple Python Implementation

from heapq import heappush, heappop,heapify

heap = [26,19,7,4,2,25,5,1,1]
heapify(heap)

print("The heap is :\n>>> ",heap)
heappush(heap,9)

print("After inserting 9 \n>>> ",heap)
root = heappop(heap)

print("The popped value: ",root)
print("The left over heap: \n>>> ",heap)

Note: By default, the heap created is min-heap. in case max-heap implementation is needed, we can use this library instead or multiply our value with -1:

https://pypi.org/project/heapq_max/

Hope it helps to get started with Heap. Cheers! 😊