# Recursion in Python

Recursion is a technique where a function makes a call to itself. Recursion breaks the problem into smaller ones and is easier to use. In recursion, the same operation is performed multiple times with the smaller inputs to make the problem smaller.

We use recursion with data structures like trees, graphs and also with different algorithms such as the divide and conquer algorithm, greedy algorithm, and dynamic programming.

### Working of Recursion

There are three conditions that we should follow while working with recursion.

• A base condition, to exit from an infinite loop. A base condition is very important for a recursive function to terminate the function call, if not provided the function will call itself infinitely.
• A function call, where a function calls itself with smaller values.
• A condition for unintentional cases, to check if the input is valid or not.

Recursion uses a stack memory to keep the track of the data when a function call is made recursively. Let us consider the following example. As soon as we call the method_1, the first statement in the method_1 is to call the method_2. Now, the control of the program moves to method_2.

After completing the execution of method_2, the control needs to come back to method_1 to execute the rest of the code. The system needs to store the method_1 somewhere to execute the rest of the code.

Hence, the system pushes the method_1 to stack memory. In this way, the system remembers that it needs to execute the remaining code of method_1.

``````def method_1():
method_2()
print("This is First Method")
def method_2():
print("This is Second Method")``````

### Recursion Example

Let us consider an example to find the factorial of a number using recursion. In mathematics, the factorial of a number n(denoted as n!) is the product of all the integers from 1 to that number. The factorial of numbers 1 and 0 is 1 and the factorial for negative numbers or floating-point numbers are not defined.

``````n! = n *  (n-1) * (n-2) … 3 * 2 *  1
Example,
5! = 5 * 4 * 3* 2* 1 = 120``````

Mathematically,

``````fact(n)  = n *  (n-1) * (n-2) … 3 * 2 *  1 -----eq(1)
fact(n-1) = (n-1) * (n-2) … 3 * 2 *  1     ------eq(2)
From eq(1) and eq(2):
fact(n) = n* fact(n-1)``````

In the following example, we calculate the factorial of the number 4.

• Base Condition: The smallest possible input for the factorial of a number is 0 and 1. Hence, the recursion stops when the number is reduced to 0 or 1. This is the base condition.
• Recursive case: If the number is greater than 1, the function makes a recursive call fact(n) = n* fact(n-1) to itself.
• Unintentional cases: The factorial for negative numbers or floating-point numbers are not defined.
``````def factorial(n):
if (n < 0 or int(n) != n):   #unintentional cases
return "Not defined"    #negative or floating point values
if (n == 1 or n == 0): #base condition
return 1
else:
return n * factorial(n-1) # recursive calls

x = factorial(4) #calling function factorial
print(x) ``````

Let us look at the step-by-step process.

### Types of Recursion

Recursion can be broadly classified into two types.

1. Direct Recursion
2. Indirect Recursion

### Direct Recursion:

In the direct recursion technique, the function calls itself repeatedly until a base condition is satisfied. The direct recursion is again subdivided into different categories as follows.

### Tail Recursion:

If a recursive function is calling itself and the recursive call is the last statement in the function, then it is called Tail recursion.

After the recursive call, the function doesn’t execute any statements or instructions. In tail recursion, all the operations are performed at the calling time and no operations are performed at the returning time.

In the following example, the function my_func() executes the print statement in the calling time and then makes the recursive call at the end.

``````def  my_func(n):
if (n > 0):
print(n, end =  " ")
my_func(n-1)
my_func(4)

#Output: 4 3 2 1``````

If a recursive function is calling itself and the recursive call is the first statement in the function, then it is called Head recursion. There is no statement or instructions before the recursive call. In head recursion, all the operations are performed at the returning time and no operations are performed at the calling time.

In the following example, the function my_func() makes a recursive call to itself and then executes the print statement in returning time.

``````def  my_func(n):
if (n > 0):
my_func(n-1)
print(n, end = " ")
my_func(4)

#Output: 1 2 3 4``````

### Tree Recursion:

If a function is calling itself more than one time, then it is known as Tree Recursion. In the following example, we make a call to my_func() recursively two times.

``````def  my_func(n):
if (n > 0):
print(n, end= " ")
my_func(n-1) #first call
my_func(n-1) #second call
my_func(4)

#Output: 1 2 3 4``````

### Nested Recursion:

In nested recursion, a recursive call takes a recursive call as a parameter, i.e. recursion inside recursion.

In the following example, my_func(my_func(n + 11)) the recursive call takes another recursive call as a parameter.

``````def  my_func(n):
if (n > 100):
return n - 10
else:
return my_func(my_func(n + 11))
print(my_func(95))

#Output: 91``````

### Indirect Recursion:

In the indirect recursion, more than one function calls one another circularly. For example, consider three functions func_A, func_B, and func_C. The func_A calls func_B, func_B calls func_C, and func_C calls func_A circularly.

``````def func_A(n):
if n > 0:
print(n, end = " ")
func_B(n - 1) #calling func_B

def func_B(n):
if n > 0:
print(n, end = " ")
func_C(n - 1) #calling func_C

def func_C(n):
if n > 0:
print(n, end = " ")
func_A(n // 2) #calling func_A

func_A(20)

#Output: 20 19 18 9 8 7 3 2 1 ``````

### Different Cases to use/avoid recursion

#### Cases to use recursion

• If a problem can be broken down into similar sub-problems.
• If the time complexity and space is not an issue and,
• When we need a quick solution instead of an efficient one.
• The recursion technique can also be used with different data structure trees, graphs, and also with different algorithms such as the divide and conquer algorithm, greedy algorithm, and dynamic programming.

#### Cases to Avoid recursion

• If a problem cannot be broken down into similar sub-problems.
• If we need an efficient solution and time & space complexity are important to us.

### Fibonacci number

In this example, we use recursion to find the Fibonacci series. A Fibonacci series is a series of numbers in which each number is the sum of two preceding numbers. The sequence starts from 0 and 1. The Fibonacci sequence is given as follows.

``0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...``

In the above series, consider the number 8 it is the sum of two preceding numbers 3 and 5(3 + 5 =8).

• Base condition: The series starts from 0 and 1. These are reserved numbers. Hence, fib(0) = 0 and fib(1) = 1.
• Recursive case: fib(n) = fib(n-1) + fib(n-2) where fib(n). denotes nth number in Fibonacci series.
• Unintentional cases: The number n should not be a negative number or floating-point value.
``````def fib(n):
if n < 0 or int(n) != n:
return "Not defined"
elif n == 0 or n == 1 :
return n
else:
return fib(n-1) + fib(n-2)

print(fib(4))#prints Fibonacci of 4th number in series
#Output: 3

print(fib(0))#prints Fibonacci of 0th number in series
#Output: 0

print(fib(-8))#prints Fibonacci of negative number
#Output: Not defined

print(fib(1.5))#prints Fibonacci of floating-point value
#Output: Not defined``````

Let us understand the example by tracing the program for fib(4).

### Sum of digits of a positive number

Consider a number num = 3214. The sum of digits in the number num is (3 + 2 + 1 + 4 = 10). Now, to obtain each digit separately, we perform the modular and division operation.

The (num % 10) gives the last digit, and the statement (num // 10) removes the last digit and returns the remaining part of the number. The function is then called recursively for the remaining digits.

In the following code, we declare a user-defined function sum_digits() that takes a number num as a parameter.

• Base Condition: The smallest possible input for the recursive function sum_digits is 0. Hence, the recursion process stops when the number is reduced to 0.
• Recursive case: We call the function recursively for the remaining part of the number, excluding the last digit. The recursive call is sum_digits(num) = (num%10) + sum_digits(n//10).
• Unintentional cases: The number num should not be a negative number or a floating-point value. Otherwise, the program returns the unexpected output.
``````def sum_digits(num):
if num < 0 or int(num) != num:
return "Not defined"
elif num == 0:
return 0
else:
return (num % 10) + sum_digits(num//10)

print(sum_digits(3214)) #Positive number
#Output: 10

print(sum_digits(-23))  # Negative number
#Output: Not defined

print(sum_digits(76.87)) #Floating-point value
#Output: Not defined``````

### Power of a number

The power of a number can be defined as, multiplying a number repetitively with itself. Consider a number x, when x is raised to the power of n, we multiply x with itself n number of times. Here, x represents the base, and n represents the exponent.

Mathematically,

``````xn   =  x * x * x … (n times)
x4 =  x * x * x* x
X3 = x * x * x
Now, from eq(1) and eq(2)
X4 = x * x3

Hence, we can write
xn = x * x(n-1)``````

Program

In the following program, we declare a user-defined function power() that takes the base and exp value as parameters.

• Base Condition: Any number raised to the power of 0 is 1. Hence, if the exponent value is reduced to 0, we return 1 and the recursion process stops.
• Recursive case: The recursive call is given as base * power(base, exp-1). In each recursive call, we reduce the value of the exp by 1.
• Unintentional cases: If the value of exp is negative or a float value, the function will call itself infinitely. Hence, the exp should not be a negative number or a floating-point value.
``````def power(base, exp):
if exp < 0 or int(exp) != exp:
return "Enter a positive exponent value"
elif exp == 0:
return 1
else:
return base * power(base, exp - 1)
print(power(3, 4))
#Output: 81

print(power(3, -2))
#Output: Enter a positive exponent value``````

### GCD(Greatest common divisor) of two numbers

The greatest common divisor for two or more integers is the largest common factor, that divides each of the integers.

Consider two integers 36 and 60. We find all the factors for both the integers 36 and 60. The multiplication of all the common factors of both the numbers gives the greatest common divisor.

``````36 = 2 * 2 * 3 * 3
60 = 2 * 2 * 3 * 5
GCD = multiplication of common factors
= 2 * 2 * 3
= 12``````

Another way to find the greatest common factor is the Euclidean algorithm. Consider two integers 60 and 36. The algorithm to find gcd(60, 36) is given below.

``````a = 60, b = 36
a/b => 60/36 = 1 and rem = 24

Exchange ( a = b) and (b = rem)
a = 36, b = 24
36/24 = 1 and rem = 12

Exchange ( a = b) and (b = rem)
a = 24 , b = 12
24/12 = 2 and rem= 0

Exchange (a = b) and (b =rem)
a = 12 and b = 0

The division is not possible further.
Hence if b becomes 0, we return a as gcd.

Thus, GCD of (60, 36) is 12.``````

Program

Consider a user-defined function gcd() that takes two numbers a and b as parameters. The function is called recursively to obtain the greatest common divisor.

• Base condition: If b == 0, return a.
• Recursive case: Divide a/b and get the remainder. Now, exchange a with b, and b with remainder and call the function recursively. The recursive call is given as gcd(b, a%b).
• Unintentional case: We know that, gcd(a, b) = gcd(-a, b) = gcd(a, -b) = gcd(-a, -b).
• If we get any negative number as input, we convert it to their absolute values to avoid unexpected output.
• Now, the gcd is defined for integer values. To avoid floating-point values, we check if the number is not an integer. If the condition is True, then we ask the user to enter an integer value.
``````def gcd(a , b):
if int(a) != a or int(b) != b:
return "Enter integer values"
if a < 0:
a = -a
if b < 0:
b =-b
if b==0:     #base condition
return a
else:
return gcd(b, a%b)  #recursive call

print(gcd(60, 36))
#Output: 12

print(gcd(60, -36))
#Output: 12

print(gcd(60, 3.6))
#Output: Enter integer values``````

### Decimal number to Binary

We can convert the decimal number to binary by successively dividing the number by 2, and printing the remainder in reverse order. In the following example, we obtain the binary value of the number 10.

• Step 1: Divide the number by 2
• Step 2: Get the integer quotient for next iteration.
• Step 3: Get the remainder for binary digit.
• Step 4: Repeat the process until the quotient becomes 0.

The binary number of 10 is 1010. To concatenate all the digits in reverse order, we multiply the remainder with 10, to add a new place and add the previous remainder. This can be written as f(n) = (n %10) + 10 * f(n//2).

Program

In the following example, we use a user-defined function decimal_binary() and take a number n as parameter.

1. Base condition: If the value of n is equal to 0, return 0.
2. Recursive case: decimal_binary(n) = (n%2) + 10*decimal_binary(int(n/2))
3. Unintentional cases: If the number n is of float data type, the program gives unexpected output.
``````def decimal_binary(n):
if int(n) != n:
return "Parameter can be only be an integer value"
if n == 0:
return 0
else:
return (n % 2) + 10 * decimal_binary(int(n/2))

print(decimal_binary(10)) #Positive decimal value
#Output: 1010

print(decimal_binary(-10)) # Negative decimal value
#Output: 1010

print(decimal_binary(1.2)) # Floating point value
#Output: Parameter can be only be an integer value``````

### FAQ on Recursion

#### How to break out of recursion in python?

The following is the recursion program to print the factorial of a number. The function `fac(n)` will be called till variable n becomes 0. The recursion breaks out when the base condition(n==1) is met.

``````def fac(n):
pass
if n==0:
return 1
else:
return n*fac(n-1)
fac(3)``````

Output

``6``

#### How to call a recursive function in python?

In the below code the function `recursion(n)` is called again within the same function block. The variable n is decremented and passed as a parameter to the same function until the variable becomes 1.

``````def recursion(n):
if n <= 1:
return n
else:
return(recursion(n-1) + recursion(n-2)) #recursive call

n_terms = 6
if n_terms <= 0:
print("Invalid input ! Please input a positive value")
else:
print("Fibonacci series:")
for i in range(n_terms):
print(recursion(i))``````

Output

``````Fibonacci series:
0
1
1
2
3
5``````

#### How to end recursion in python?

If the solution to the problem shrinks and moves towards a base case with each recursive call, the recursive function finishes. If the base case is not met in the calls, a recursion can end up in an infinite loop.

In the below code, the variable time is decremented each time the function` startcountdown(time) `is called and the recursion ends when the function meets the base condition (i.e time=0).

``````def startcountdown(time):
print(time)
if time == 0:
return             # Terminate recursion
else:
startcountdown(time - 1)   # Recursive call
startcountdown(5)``````

Output

``````5
4
3
2
1
0``````

#### How to find factorial using recursion in python?

A number’s factorial is the product of all numbers from 1 to that number. The `factorial()` method in the following program takes one parameter and keeps running itself, reducing the value by one until it reaches 1.

``````def findfact(num):
if num == 1:
return 1
else:
return (num * findfact(num-1))
num = 7
print("The factorial of", num, "is", findfact(num))``````

Output

``The factorial of 7 is 5040``

#### How to reverse a list in python using recursion?

In the below code, the original list, first and the last index is passed as a parameter. The first element in the list is stored at the last index of the list. And the last element is stored at the first index of the list. The function is recursively called by incrementing and decrementing the index.

``````def reversing_the_list(List, i, j):
if(i < j):
temp = List[i]
List[i] = List[j]
List[j] = temp
reversing_the_list(List, i + 1, j-1)

List = []
size = int(input("Enter the size of List: "))
for i in range(1, size + 1):
value = int(input("Enter the Value of %d Element in List: " %i))
List.append(value)
print("\nOriginal List: ",List)

reversing_the_list(List, 0, size - 1)
print("\nReversed List =  ", List)``````

Output

``````Enter the size of List: 6
Enter the Value of 1 Element in List: 12
Enter the Value of 2 Element in List: 3
Enter the Value of 3 Element in List: 5
Enter the Value of 4 Element in List: 7
Enter the Value of 5 Element in List: 98
Enter the Value of 6 Element in List: 5

Original List:  [12, 3, 5, 7, 98, 5]

Reversed List =   [5, 98, 7, 5, 3, 12]``````

#### How to reverse a string using recursion in python?

In the below `reverse_the_string(string)` function, the string is passed as an argument to a recursive function to reverse the string. The base condition returns the string if the string length is equal to zero.

Otherwise `reverse_the_string(string)` function is called recursively to slice the string apart from the first character and concatenate the first character to the end of the sliced string.

``````def reverse_the_string(string):
if len(string) == 0:
return string
else:
return reverse_the_string(string[1:]) + string[0]
res = input('Enter the string to be reversed : ')
print('REVERSED STRING IS ',reverse_the_string(res))``````

Output

``````Enter the string to be reversed : Hello World
REVERSED STRING IS  dlroW olleH``````

#### How to stop a recursive function in python?

Throwing an exception and catching it at the top level is one approach to get out of a recursive procedure in Python.

``````def exception_problem(lst):
def solve_rec(l):
'''has implented the statement that may throw an exception '''
try:
solve_problem(lst)
return True
except:
return False``````

#### Are python programs recursive or iterative?

Python is both iterative and recursive, but iteration is faster and uses less memory than recursion since Python does not keep track of past iteration steps. In practice, recursions can do practically all iterations and vice versa.

In recursion the same function is called again, recursion makes some tasks easier to complete than iteration. Some jobs can be accomplished more elegantly by iteration rather than recursion. Iteration is preferable over recursion in terms of time complexity and memory constraints.

In the following code, the input() method is used to get user input. While loop is used to iterate through the numbers and print the list of numbers from 1 till entered value.

``````n = int(input("Enter any Number: "))

print("Numbers till ", n)
i=1
while(n > i):
print (i, end = '  ')
i=i+1``````

Output

``````Enter any Number: 6
Numbers till 6
1  2  3  4  5  ``````

#### Are recursions faster than for loops in python?

Recursion isn’t faster than loops because loops have built-in support in CPUs, but recursion uses the slower function call/return mechanism. When the code is properly written, however, a good compiler may make recursion as fast as loops. The problem with recursion is that it involves many redundant calls which cause the program to scale exponentially with N.

Use the input() method in Python to get user input. Iterate through for loop with the number entered by the user. The loop iteration value is increased by one, and the loop iteration value is printed.

``````n = int(input("Enter any Number: "))

print("Numbers from 1", "to", n)

for i in range(1, n + 1):
print (i, end = '  ')``````

Output

``````Enter any Number: 7
Numbers from 1 to 7
1  2  3  4  5  6  7  ``````

#### Can a class be recursive in python?

It is a recursive object when an object of one class has an attribute value of that same class. In the following code, the class sample has `recur()` function as a member of that class.

The same function is called within the same class in the return statement. The parameter self in `recur() `function passes the same class as a parameter. The` recur(self,num) `function is used to print the product of ‘num’ numbers.

``````class sample:
def recur(self, num):
print(num, end="")
if num > 1:
print(" * ",end="")
return num * self.recur(self, num-1)
print(" =")
return 1

def main():
a = sample()
print(sample.recur(sample, 10))

main()``````

Output

``````10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 =
3628800``````

#### Can python print inside a recursion?

Yes, the print statement can be used inside a recursive function. The following code is used to print the pattern horizontally.

``````import sys
def printpattern(n):
'prints the nth pattern'
if n == 0:    # base case
print(0, end=' ')
else:
pattern(n-1)
print(n, end=' ')
pattern(n-1)
pattern(2)``````

Output

``0 1 0 2 0 1 0``

#### Does python has a recursion depth limit?

Executing recursive function in Python on a large input ( > 10^4), will encounter a “maximum recursion depth exceeded error”. Python’s recursion limit is commonly set to a small number (about 10^4). This means that if you give the recursive function a large input, you’ll get an error.

``````def fact(n):
if(n == 0):
return 1
return n * fact(n - 1)
f = int(input('Enter the number: \n'))
print(fact(f))``````

Output

``````Enter the number : 1000
Recursion error : Maximun recursion depth exceeded in comparison``````

Using the `setrecursionlimit()` function is used to increase the recursion limit and can avoid this error.

``````import sys
sys.setrecursionlimit(10**6)
def fact(n):
if(n == 0):
return 1
return n * fact(n - 1)
f = int(input('Enter the number: \n'))
print(fact(f))``````

Output

``````Enter the number:
1000
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168....``````

#### Does python support tail recursion?

Yes, python supports tail recursion. Tail recursion is a recursive function where the recursive call is made at the end of the function.

The following code is used to print the number in decreasing order. The function prints the number, and at the end of the function recursive call is made by decrementing the number. The function is executed till the base case is met (till the number becomes zero).

``````def printdecreasingorder(n):
if (n < 0):
return
print(n, end=' ')
# The recursive call is made at end of the function
prints(n-1)
printdecreasingorder(4)``````

Output

``4 3 2 1 0 ``

#### How insertion sort works in python using recursion?

In a recursive insertion algorithm, we keep processed elements sorted and add new elements to the inserted array one by one. In the below code, if the array size is 1 or smaller, we just return the array without any sorting. For the arrays with sizes greater than one, recursively sort the first n-1 elements and insert the last element at its correct position in a sorted array.

``````def RecursiveInsertionSort(arr,n):
if n<=1:
return

RecursiveInsertionSort(arr,n-1)
last = arr[n-1]
j = n-2
while (j>=0 and arr[j]>last):
arr[j+1] = arr[j]
j = j-1

arr[j+1]=last
def printSortedArray(arr,n):
for i in range(n):
print(arr[i]),

arr = [123,8,56,7,45,32,6,7]
n = len(arr)
RecursiveInsertionSort(arr, n)
printSortedArray(arr, n)``````

Output

``````6
7
7
8
32
45
56
123``````

#### How to access files recursively in python?

walk() function allow recursive browsing of the directory tree to find files in Python. The `walk() `function in the following code, traverse through the directory ‘src’ and prints down all the file name that has .txt extension in that directory.

``````import os

# Using os.walk()
for dirpath, dirs, files in os.walk('src'):
for filename in files:
fname = os.path.join(dirpath,filename)
if fname.endswith('.c'):
print(fname)``````

Output

``````./src/add.txt
./src/sample.txt
./src/sub/result.txt``````

#### How to add two numbers in python using recursion?

In the below code, variables num1 and num2 are used to get input from the user. The num2 is decremented and passed as a parameter recursively to the function till the variable num2 becomes 0. One is added to the result of the function in every recursive call. And the result is printed.

``````def recursivesum(num1,num2):
if(num2==0 ):
return num1;
else:
return(1+recursivesum(num1,num2-1));
x=int(input("Enter first number: "))
y=int(input("Enter second number: "))

print("Sum of two numbers are: ",recursivesum(x,y))``````

Output

``````Enter first number: 10
Enter second number: 10
Sum of two numbers are:  20``````

#### How to calculate if number is perfect factorial in python?

In the below code, To find whether the given number is a perfect factorial number or not, the variable num is divided by the variable i, and floor value is found. And at the end of the while loop, if the variable num is 1, then it is a perfect factorial number.

``````def isFactorial(num) :
i = 1;
while(True) :
if (num % i == 0) :
num //= i;
else :
break;
i += 1;
if (num == 1) :
return True;
else :
return False;
n = 7;
ans = isFactorial(n);
if (ans == 1) :
print(n," is a factorial number");
else :
print(n," is not a factorial number");``````

Output

``7  is not a factorial number``

#### How to check if an integer is prime number using recursion in python?

In the below code, the number is taken as input from the user. The number is passed as an argument to a recursive function and the divisor is initialized to NULL. The number’s divisors are then checked via recursion, and True or False is returned. And the result is printed.

``````def IsPrimeOrNot(num, div = None):
if div is None:
div = num - 1
while div >= 2:
if num % div == 0:
print(num+" is not a prime number")
else:
return check(num, div-1)
else:
print(num+" is a prime number")
n=int(input("Enter number: "))
IsPrimeOrNot(n)``````

Output

``````Enter number: 78
78 is not a prime number``````

#### How to check recursion count in python?

In the below code the variable count is used to maintain the number of times recur() function is executed. Each time when the `recur()` function is called, the count is incremented.

``````def recur(n, count=0):
if n == 0:
return "Finished count %s" % count
return recur(n-1, count+1)
recur(6)``````

Output

``'Finished count 6'``

#### How to compare elements of a string recursively in python?

In the below code, the `contains(text, pat, text_index, pat_index)` function returns true if the pattern matches with the text and if the current character is the last character of the pattern. It returns false if the current character is the last character of the text, but the pattern has more characters. In all other cases, the recursive call is made.

``````def stringMatch(text, pat, text_index, pat_index):
if text_index == len(text) and pat_index != len(pat):
return 0

# Else If last character of pattern reaches
if pat_index == len(pat):
return 1

if text[text_index] == pat[pat_index]:
return stringMatch(text, pat, text_index+1, pat_index+1)

return 0

def contains(text, pat, text_index, pat_index):
if text_index == len(text):
return 0
if text[text_index] == pat[pat_index]:
if stringMatch(text, pat, text_index, pat_index):
return 1
else:
return contains(text, pat, text_index+1, pat_index)

return contains(text , pat, text_index+1, pat_index)

print(contains("Welcome all", "come", 0, 0))
print(contains("Timeisprecious", "area", 0, 0))
print(contains("quiztime", "quiz", 0, 0))``````

Output

``````1
0
1``````

#### How to convert decimal to binary in python using recursion?

By dividing a decimal value by 2 and displaying the remainder in reverse order, the decimal number is converted to binary.

``````def decimalToBinary(n):
if n > 1:
decimalToBinary(n//2)
print(n % 2,end = '')
dec = 12
decimalToBinary(dec)
print()``````

Output

``1100``

#### How to convert for loop to recursion in python?

Identify the main loop. The base case is the loop condition, and the recursive case is the loop body. The iterative local variables become parameters in the recursive version. The variable str which is used as a local variable in for loop is passed as a parameter in the recursive function.

``````#Iterative approach
def reverse_string_iterative(str):
str1 = ""
for i in str:
str1 = i + str1
return str1
str = "Technology"
print("The original string is: ",str)
print("The reverse string is",reverse_string_iterative(str))
#recursive approach
def reverse_string_recursive(str):
if len(str) == 0:
return str
else:
return reverse_string_recursive(str[1:]) + str[0]
str = "Helloworld"
print ("The original string  is : ", str)
print ("The reversed string(using recursion) is : ", reverse_string_recursive(str))``````

Output

``````The original string is:  Technology
The reverse string is ygolonhceT
The original string  is :  Helloworld
The reversed string(using recursion) is :  dlrowolleH``````

#### How to create infinite recursion in python?

In Python, unlike several functional languages, an endless recursive loop is not possible. When the recursion depth hits around 1000, it will throw an exception (by default, this can be changed using `sys.setrecursionlimit`). In the below code, the recursion limit is set to 10^6, and the function `sumofnum(n`) will return the sum of numbers.

``````import sys
sys.setrecursionlimit(10**6)
def sumofnum(n):
if(n == 1):
return 1
return n + sumofnum(n - 1)
f = int(input('Enter the number: \n'))

print(sumofnum(f))``````

Output

``````Enter the number:
1000
500500``````

#### How to define functions recursively in python?

In python a recursion function is a function, that calls itself. The syntax for the recursive function is as follows.

``````def recurse():
....
recurse()
....
recurse()``````

#### How to do multiplication with recursion in python?

In the below code, the variables num1 and num2 are swapped if, num1 is less than num2. Then the product is recursively found num2 times, the sum of num1. If either num1 or num2 becomes 0, zero is returned.

``````def multiplication( num1 , num2 ):
if num1 < num2:
return multiplication(num2, num1)
elif num2 != 0:
return (num1 + multiplication(num1, num2 - 1))
else:
return 0
x = 5
y = 78
print( multiplication(x, y))``````

Output

``390``

#### How to find gcd in python using recursion?

In the below code, two numbers are taken as input from users and are passed as arguments to the function. when the second number becomes zero, the first number is returned.

Else recursively call the function with the arguments as the second number and the remainder when the first number is divided by the second number. After the recursive calls, the first number becomes the GCD of the two numbers.

``````def GreatestCommonDivisor(a,b):
if(b==0):
return a
else:
return GreatestCommonDivisor(b,a%b)
num1=int(input("Enter first number:"))
num2=int(input("Enter second number:"))
GCD=GreatestCommonDivisor(num1,num2)
print("GCD of two numbers : ")
print(GCD)``````

Output

``````Enter first number:50
Enter second number:25
GCD of two numbers :
25``````

#### How to remove a letter from a string using recursion in python?

Get the string str and the character X that has to be deleted. Iterate for all the characters in the string recursively. If the length of the string str becomes 0, then the method returns the empty string.

``````def removeCharRecursive(str, X):
if (len(str) == 0):
return ""
if (str[0] == X):
return removeCharRecursive(str[1:], X)
return str[0] + removeCharRecursive(str[1:], X)
str = "TechnologyFreak"
X = 'e'
str = removeCharRecursive(str, X)
print(str)``````

Output

``TchnologyFrak``

#### How to interleave two strings in python recursively?

Let s and t be the two strings you want to interleave. We’ll use recursion to generate all possible interleaving combinations for these two strings. We repeat this recursion until all characters in both strings have been used, at which point we save the result in a list of strings lis, as seen in the code below.

``````def interleavestring(s, t, res, i, j, lis):
if i == len(s) and j == len(t):
lis.append(res)
return
if i < len(s):
interleavestring(s, t, res + s[i], i + 1, j, lis)
if j < len(t):
interleavestring(s, t, res + t[j], i, j + 1, lis)

l = []
s = "ab"
t = "cd"
interleavestring(s, t, "", 0, 0, l)
print(l)``````

Output

``['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']``

#### How to print recursively on the same line in python?

By default all the recursive function prints the result in the new line. In the below code, using the parameter, end=’ ‘ in `print()` statement, the output of the recursive function is printed on the same line.

``````import sys
def pattern(n):
'prints the nth pattern'
if n == 0:    # base case
print(0, end=' ')
else:    #recursive step: n > 0
pattern(n-1)
print(n, end=' ')
pattern(n-1)
pattern(2)``````

Output

``0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 ``

#### How to recursive copy in python?

The shutil module helps in the process of copying and removal of files and directories. The `shutil.copytree()` method copies a directory tree rooted at source (src) to the destination directory in a recursive manner. The destination target directory must not already exist.

``````import shutil
path = 'C:/sample/CherCher'
src = 'C:/sample/CherCher/src'
dest = 'C:/sample/CherCher/dest'
destination = shutil.copytree(src, dest) ``````

Output

#### How to recursively find biggest number in list using python?

If there is only one element in the list, that element is the maximum. If the list contains many elements, the first element in the list is considered to be the maximum of the list element. To discover the maximum of those items, call Max on the rest of the elements in a recursive manner.

``````def Max(list):
if len(list) == 1:
return list[0]
else:
m = Max(list[1:])
return m if m > list[0] else list[0]

def main():
list = input(" please enter a list of numbers: ")
print("the largest number is: ", Max(list))

main()``````

Output

``````please enter a list of numbers: 2 3 4 9 1
the largest number is:  9``````

#### How to recursively loop through a file object in python?

The `walk()` generates the file names in a directory tree by walking the directory tree either top-down or bottom-up. In the below code the topdown approach is set as false. And all the directories, subdirectories, and files are printed.

``````import os
for root, dirs, files in os.walk(".", topdown=False):
for name in files:
print(os.path.join(root, name))
for name in dirs:
print(os.path.join(root, name))``````

Output

``````.\.android\avd
.\.config\configstore\update-notifier-npm.json
.\.config\configstore
.\.dotnet\TelemetryStorageService\20210503050054_494f7f3549ac45a5aaea6456822f10a9.trn
.\.dotnet\TelemetryStorageService\20210503050054_d96559082be849db82d30f22f1011298.trn
...``````

#### How to recursively flip a list in python?

In the below code, elements of the list are got as input from the user and are passed into the `flip_list()` function. The` flip_list() `function flips each list element with the next list element until the whole list is flipped in the reverse order.

``````def flip_list(NumList, i, j):
if(i < j):
temp = NumList[i]
NumList[i] = NumList[j]
NumList[j] = temp
flip_list(NumList, i + 1, j-1)
NumList = []
Number = int(input("Enter the Total Number of List Elements: "))
for i in range(1, Number + 1):
value = int(input("Enter the Value of %d Element: " %i))
NumList.append(value)
print("\nOriginal List: ",NumList)
flip_list(NumList, 0, Number - 1)
print("\nThe Result of flipping a List =  ", NumList)``````

Output

``````Enter the Total Number of List Elements: 4
Enter the Value of 1 Element: 2
Enter the Value of 2 Element: 3
Enter the Value of 3 Element: 45
Enter the Value of 4 Element: 7

Original List:  [2, 3, 45, 7]

The Result of flipping a List =   [7, 45, 3, 2]``````

#### How to recursively reverse a string in python?

In the below code, a string must be entered by the user. To reverse the string, the string is supplied as an argument to a recursive function. The base condition of the function is that the string is returned if the length of the string is equal to 0.

If the value is not 0, the reverse function is used recursively to slice the string except for the first character and concatenate the first character to the end of the sliced string. The string is reversed and printed.

``````def reverse_string_recursion(string):
if len(string) == 0:
return string
else:
return reverse_string_recursion(string[1:]) + string[0]
a = input("Enter the string to be reversed: ")
print(reverse_string_recursion(a))``````

Output

``````Enter the string to be reversed: CherCherTech
hceTrehCrehC``````

#### How to recursively unzip a file in python?

Unzip all zip files in the directory (and subdirectories) and repeat until there are no more zip files. If the zip files contain zip files, you’ll need to repeat them. When extracting the zip file, we should write the inner zip files to memory instead of them on disk. To do this, we use `BytesIO.`

``````import os
import io
import zipfile
def extract_zipfile(filename):
z = zipfile.ZipFile(filename)
for f in z.namelist():
# get directory name from file
dirname = os.path.splitext(f)[0]
# create new directory
os.mkdir(dirname)
# read inner zip file into bytes buffer
zip_file = zipfile.ZipFile(content)
for i in zip_file.namelist():
zip_file.extract_zipfile(i, dirname)
extract_zipfile("PassportManagement_Template.zip")``````

Output

``````sample/
sample.txt
entity/
entity.xml
results/
result.txt``````

#### How to recursively visit all subdirectories using python?

The `os.walk()` function walks through the directory tree in a top-down or bottom-up approach to generate file names. It returns a 3-tuple for each directory in the tree rooted at the directory top: `(dirpath, dirnames, filenames)`. The `dirpath `is a string that represents the directory’s path. The `dirnames `list (excluding ‘.’ and ‘..’) is a list of the names of the subdirectories in `dirpath`.

``````import os
path = "./TEST"
for root,d_names,f_names in os.walk(path):
print(root, d_names, f_names)
fname = []
for root,d_names,f_names in os.walk(path):
for f in f_names:
fname.append(os.path.join(root, f))

print("fname = %s" %fname)``````

Output

``````./TEST ['D1', 'D2'] ['root.txt']
./TEST/D1 [] ['d1_b.txt', 'd1_a.txt']
./TEST/D2 [] ['d2_a.txt']
fname = ['./TEST/root.txt', './TEST/D1/d1_b.txt', './TEST/D1/d1_a.txt', './TEST/D2/d2_a.txt']``````

#### How to remove folders recursively using python?

The folders and it’s contents can be recursively removed used `shutil.rmtree().` The path of the folder is passed as an argument to `rmtree()`. The below code, deletes all the contents of a directory using` shutil.rmtree() `and handles exceptions.

``````import shutil
dirPath = 'C:/sample/CherCher/'
try:
shutil.rmtree(dirPath)
except:
print('Error while deleting directory')``````

Output

#### How to Reverse a List using Recursion in Python?

In the below code, elements of the list are got as input from the user and are passed into the` reverse_list()` function. The` reverse_list()` function moves each list element with the next list element until the whole list is in reverse order.

``````def reverse_list(NumList, i, j):
if(i < j):
temp = NumList[i]
NumList[i] = NumList[j]
NumList[j] = temp
reverse_list(NumList, i + 1, j-1)
NumList = []
Number = int(input("Enter the Total Number of List Elements: "))
for i in range(1, Number + 1):
value = int(input("Enter the Value of %d Element: " %i))
NumList.append(value)
print("\nOriginal List: ",NumList)
flip_list(NumList, 0, Number - 1)
print("\nThe Result of flipping a List =  ", NumList)``````

Output

``````Enter the Total Number of List Elements: 3
Enter the Value of 1 Element: 21
Enter the Value of 2 Element: 3
Enter the Value of 3 Element: 65

Original List:  [21, 3, 65]

The Result of flipping a List =   [65, 3, 21]``````

#### How to reverse a nested list in python using recursion?

In the below code, a recursive function `reversenestedList(L)` is defined that checks if the element is itself a list. If it is not a list, the element is added to the result, or a recursive call is made to the function with the list element as an argument.

``````A = [1, 4, [51, 32], 4, [51, [521, [12, 25, 56, [444, 151]],522], 83], 6]
def reversenestedList(L):
if len(L) == 0:
return
if len(L) == 1:
if isinstance(L[0], list):
return [reversenestedList(L[0])]
else:
return L
else:
return reversenestedList(L[1:]) + reversenestedList(L[:1])
print(A)
print(reversenestedList(A))``````

Output

``````[1, 4, [51, 32], 4, [51, [521, [12, 25, 56, [444, 151]], 522], 83], 6]
[6, [83, [522, [[151, 444], 56, 25, 12], 521], 51], 4, [32, 51], 4, 1]``````

#### How to reverse a number in python using recursion?

In this Python program, we read a number from the user and then pass this number to a recursive function `reverseanum()`. The argument r is initially passed a 0. In the recursive call, one of the arguments is: number is divided by 10. The other argument: r is multiplied by 10 and the remainder of the number is added.  This will return the reversed number when the base case is met.

``````def reverseanum(n, r):
if n==0:
return r
else:
return reverseanum(n//10, r*10 + n%10)
number = int(input("Enter number: "))
reversed_number = reverseanum(number,0)

print("Reverse of %d is %d" %(number, reversed_number))``````

Output

``````Enter number: 5678
Reverse of 5678 is 8765``````

#### How to search for the smallest value of the list in python using recursion?

The below code returns 0 if the list is empty. If the list has only one element, that element is returned. In other cases, the first element of the list is considered to be the minimum value(stored in variable min). Then each element of the list is recursively compared with the variable min.

The value of the variable min is swapped if any other element of the list has a smaller value than min. At the end of the recursive call, variable min holds the smallest value in the list.

``````sample = [90,-6,6,10,0,9,-2]

def findMinimuminlist(l):
if len(l) == 0:
return 0
elif len(l) == 1:
return l[0]
else:
minNumber = findMinimuminlist(l[1:])
min = l[0]
if minNumber < min:
min = minNumber
return min
print("mininum element in the list is ",findMinimuminlist(sample))``````

Output

``mininum element in the list is  -6``

#### How to sort a list in python using recursion?

In the below code, `sort_a_list(l)` function returns the same list if the list has one element or less. In other cases, each element is compared with other elements recursively and is sorted in ascending order.

``````def sort_a_list(l):
if len(l) <= 1:
return l
else:
return sort_a_list([e for e in l[1:] if e <= l[0]]) + [l[0]] +\
sort_a_list([e for e in l[1:] if e > l[0]])
sort_a_list([3, 1, 2, 4, 7, 5, 6, 9, 8])``````

Output

``[1, 2, 3, 4, 5, 6, 7, 8, 9]``

#### How to split a string using recursion in python?

In the following code, the `splitstring(str) `function splits the entire string into the different strings each of length 3. The variable beginning stores the first 3 characters in the string and the rest of the character is stored in the variable remaining.

Then the recursive call is made with the string stored in the variable remaining. The recursion stops when the string length becomes less than or equal to 3.

``````def splitstring(str):
if len(str) <= 3:
return [str]
else:
beginning = str[:3]
remaining = str[3:]
return [beginning] + splitstring(remaining)
splitstring('knowledge is power')``````

Output

``['kno', 'wle', 'dge', ' is', ' po', 'wer']``

#### How to write a recursive function in python to find palindrome?

In the below code, the user-entered string is passed an argument to `find_palindrome(s)` function. If the last letter is equal to the first letter, the function is called recursively with the argument. The list is sliced with the first character and the last character removed. The if statement is used to check if the returned value is True or False and the final result is printed.

``````def find_palindrome(s):
if len(s) < 1:
return True
else:
if s[0] == s[-1]:
return find_palindrome(s[1:-1])
else:
return False
a=input("Enter string:")
if(find_palindrome(a)==True):
print(a," is a palindrome!")
else:
print(a," is not a palindrome!")``````

Output

``````Enter string:madam

#### Check if a given number is a prime number using recursion in python?

In the below code, The number n is passed as an argument to a recursive function and the divisor count is initialized to NULL. The variable div is initialized to n-1. The number of divisors of the number is checked using recursion and either True or False is returned. And the result is printed.

``````def check_prime(n, div = None):
if div is None:
div = n - 1
while div >= 2:
if n % div == 0:
print(n," is not prime")
return False
else:
return check_prime(n, div-1)
else:
print(n," is prime")
return 'True'
n=int(input("Enter number: "))
check_prime(n)``````

Output

```Enter number: 3
3  is prime```

#### What is infinite recursion in python?

If a recursion never hits a base case, it will continue to make recursive calls indefinitely, and the program will never end. This is called infinite recursion.

``````def recursor():
recursor()
recursor()``````

Output

``RecursionError: maximum recursion depth exceeded``

#### What is mutual recursion in python

In the mutual recursive function, two functions are called recursively. The first function makes a recursive call to the second function and the second function, in turn, makes the recursive call to the first function. In the below code, the function calls function A recursively and function B calls A recursively.

``````def sampleA(n):
sampleB(n-1)
def sampleB(n):
if n <= 0:
return
else:
sampleA(n-1)``````

#### Why is recursion in python so slow?

Recursions are slow as it has to deal with a recursive call stack frame, which means it has to run more code making it slow. The recursive function has to add to the stack with each recursive call and keep the values there until the call is finished, the memory allocation is greater. Below is an example of a recursive function.

``````def decreasenumber(n):
if(n>0):
print(n-1);
decreasenumber(n-1);
decreasenumber(6)``````

Output

``````3
2
1
0``````

#### Why python doesn’t encourage recursion?

The recursive functions have very high complexity that we should avoid using. Instead, we could use python closure. In the following code the function `outer` is defined with another function `inner` inside itself, and the function `outer` returns the function `inner` as the “return value” of the function.

In this case, the nested function is called a closure in Python. On checking the “return value” of the outer function, we will find that the returned value is a function.

``````def outer():
x=1
def inner():
print(f'x in outer function: {x}')
return inner
outer()``````

Output

``<function_main_.outer.<locals>.inner>``