Recursion

1. Overview

Recursion makes the code easy to write compared to iterative whenever a given problem can be broken down into a similar sub-problem. It has some properties like below:

• The same operation is performed multiple times with different inputs
• In every step, we try to make the problem smaller
• We mandatorily need to have a base condition, which tells the system when to stop the recursion.

 

2. Description

2.1 Format of a Recursion function

2.1.1 Recursive Case

Cases when the function recurs

2.1.2 Base Case

A case where the function does not recur

# A Python 3 program to 
# demonstrate working of 
# recursion 
  
def printFun(test): 
  
    # Base Case
    if (test < 1): 
        return
    # Recursive Case
    else: 
      
        print( test,end = " ") 
        printFun(test-1) # statement 2 
        print( test,end = " ") 
        return
      
  
test = 3
printFun(test) 
  
# This code is contributed by 
# Smitha Dinesh Semwal 

2.2 Recursion vs Iteration

Particulars	Recursion	Iteration
Space efficiency	No	Yes
Time Efficiency	No	Yes
ease of code to solve sub-problem	Yes	No

3. When to use/avoid Recursion

3.1 When to use

3.1.1 When we can easily breakdown a problem into a similar subproblem

3.1.2 When we are ok with extra overhead both time and space that comes with it

If we are implementing software for an airbag of a car so then since that time is extremely crucial, So really try to avoid recursion in those kinds of applications.

3.1.3 When we need a quick working solution instead of efficient one

When we are implementing mathematical problems such as factorial using recursion it is very simple. We are done in max 2~3 lines of code though. If you would have implemented those methods using iteration instead of recursion the efficiency would have been better but we'll need to write a much longer code.

3.2 When to avoid

3.2.1 If the response to any of the above statements is NO, we should not go with recursion

• If a problem cannot be broken down into some problems
• If we are extremely cautious about time or space complexity

3. Practical Usage

3.1 Stack

3.2 Tree

Traversal, Searching, Insertion, Deletion

3.3 Sorting

Quicksort, Merge sort

3.4 Divide and Conquer

3.5 Dynamic Programming

4. Reference

https://en.wikipedia.org/wiki/Recursion

https://en.wikipedia.org/wiki/Recursion_(computer_science)

https://www.geeksforgeeks.org/recursion/

https://yourbasic.org/algorithms/time-complexity-recursive-functions/

https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

https://www.youtube.com/watch?v=X_CR07rfR4I

https://www.youtube.com/watch?v=OynWkEj0S-s