When not to use Recursion while Programming in Python?

To recurse or not to recurse, that is the question. We all know about the fun we have with recursive functions. But it has its own set of demerits too, one of which is going to be explained in this article to help you choose wisely.

Say, we need to create a function which when called needs to print the data in a linked list.

This can be done in 2 ways:

• 1. With Recursion
• 2. Without Recursion

1. With Recursion:

```
def print_linkedlist(head):

   if head is not None:
       print(head.data)
       print_linkedlist(head.next)
```

The first approach works too but if the list really long like around 1000 elements then the program will hit recursion depth and errors out. Not to forget that as the list length increases, the stack size increases linearly too.

What is Recursion Depth?

Before we go ahead, you ought to know that this problem is Python-specific. There are languages where we don’t encounter this problem but that’s not going to be discussed here.  We know that a recursive function calls itself. This means that a new function is called within the original function. Assume a linked list counting from 0 to n by 1 using the recursive code mentioned above.

The first function looks at the head node’s data in the list and then prints it. But the first function hasn’t ended yet. An old function cannot end until all the functions inside it have ended. If we observe the call stack which has the list of currently running functions:  

# the first function waiting for
# innermost functions to end
print_linkedlist()

       # the child function called 
       # within the first function
           print_linkedlist()

The call stack keeps on increasing as the older functions never end because they are waiting for the inner child functions to end. Ultimately, the call stack looks like:

# original Function
print_linkedlist()

  # first level function
  print_linkedlist()
  
    # second level function
    print_linkedlist()
    
      # third level function
      print_linkedlist()
        ……
          ……
            ……
            
              # 1000 level function – Maximum 
              # Recursion Depth Reached
              print_linkedlist()

And BAMMM!!!!! MAXIMUM RECURSION DEPTH!!

A recursion depth counts the number of active layers inside the recursive function. In Python, the default maximum recursive depth limit is 1000. The limit helps prevent stack overflow which is caused by infinite recursion.

Therefore, the second approach like the below is better as the stack size remains constant.

2.  Without Recursion/ Iteration:

```
def print_linkedlist(node):
   while node:
       print(node.data)
       node=node.next
```

Conclusion

Recursion is fun to use but you should understand when to and when not to use it. Some languages like Scala and Haskell support an interesting feature called TAIL CALL RECURSION which prevents the problem of recursion depth by ending the previous function’s call when a new call is made. But Python doesn’t support this feature. So, at least in Python, prefer the iterative approach if you think the function may hit the recursion limit.

jelonmusk

Follow

Improve