Is it safe to call a function from within the same function

Question

I've been reading up on sorting algorithms. I came across this code for Merge Sort:

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]
        #function calls itself here<<<<<<<<<<<<<<<<<<<<<<<<<
        mergeSort(L)# Sorting the first half
        mergeSort(R)# Sorting the second half

        i = j = k = 0
    
        # Copy data to temp arrays L[] and R[] 
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i] 
                i+= 1
            else: 
                arr[k] = R[j] 
                j+= 1
                k+= 1
    
        # Checking if any element was left 
        while i < len(L): 
            arr[k] = L[i] 
            i+= 1
            k+= 1
    
        while j < len(R): 
            arr[k] = R[j] 
            j+= 1
            k+= 1

# Code to print the list 
def printList(arr):
    for i in range(len(arr)):
        print(arr[i], end =" ")
    print() 

# driver code to test the above code 
if __name__ == '__main__': 
    #arr = [12, 11, 13, 5, 6, 7]
    arr = [38, 27, 43, 3, 9, 82, 10]
    print ("Given array is", end ="\n") 
    printList(arr) 
    mergeSort(arr) 
    print("Sorted array is: ", end ="\n") 
    printList(arr) 

# This code is contributed by Mayank Khanna

The function mergeSort() is called from within itself as commented above, is this good practice? I was under the impression it could cause errors.

Yes, recursion is completely normal and acceptable. Variables are kept on a stack. — alani, Aug 28 '20 at 10:13
A good and simple example of recursion is to find a factorial of a number. Using recursion sometimes is required and it's a good practice. — ThRnk, Aug 28 '20 at 10:15

Aviv Yaniv · Accepted Answer · 2020-08-28T10:42:12.610

TL;DR It's usually fine, but for some inputs can be very dangerous.

The given mergeSort function, calls itself - and this phenomenon called recursion.

What is Recursion

A common way of solving problems, where solution depends on solutions to smaller instances of the same problem; such as traversing binary trees.
Each recursive call the function parameters are pushed into the call stack, and each call has its own local variables.
Recursion can cause vulnerabilities, for example DNS open recursion.
If misused either by not defining a stop-condition or by handling input that causes a tremendous amount of recursive calls, a stack overflow will occur (which means that the call stack has been used to its maximum).
Any recursive solution can be converted to an iterative solution (solution using loops)

To Sum Up

Recursion is safe when the function invoked for a reasonable amount of time.
Python's default recursion limit is 1000, so function cannot call itself more than 1000 times.

You can validate it with getrecursionlimit:

import sys
print(sys.getrecursionlimit())

And change it with setrecursionlimit:

new_recursion_limit = 1500
sys.setrecursionlimit(new_recursion_limit)

Recursion may, and will, cause vulnerabilities, and preferably be avoided when handling user input - in favor of iterative solution.

P.S.

Now you know what our site is named after too!

`set_recursion_limit` is the naive way to increase recursion limit in Python — Mulan, Aug 28 '20 at 15:32

score 0 · Answer 2 · answered Aug 28 '20 at 10:31

There's no problem in calling a function within itself, but you just have to be extra careful about going into an infinite loop. General good practices about doing this would be only calling the function at its end (so you reduce chances of mixing up variables' values) and having some sort of if statement, or something in that sense, to provide a way out.

Is it safe to call a function from within the same function

2 Answers2