Recursion

AlgoDS/Algorithm

Recursion

데먕 2020. 1. 16. 22:56

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.