CODEWITHSUNDEEP
pythonpython-3.xfunctionrecursion
Chris Buttle
Chris Buttle

Reputation: 3

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

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.

Upvotes: 0

Views: 185

Answers (2)

Aviv Yaniv
Aviv Yaniv

Reputation: 6298

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

  1. A common way of solving problems, where solution depends on solutions to smaller instances of the same problem; such as traversing binary trees.
  2. Each recursive call the function parameters are pushed into the call stack, and each call has its own local variables.
  3. Recursion can cause vulnerabilities, for example DNS open recursion.
  4. 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).
  5. Any recursive solution can be converted to an iterative solution (solution using loops)

To Sum Up

  1. Recursion is safe when the function invoked for a reasonable amount of time.

  2. 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)
  1. 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!

Upvotes: 1

Murilo Sch&#252;nke
Murilo Sch&#252;nke

Reputation: 116

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.

Upvotes: 0

Related Questions