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.
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_1to stack memory. In this way, the system remembers that it needs to execute the remaining code ofmethod_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.
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 callfact(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.
Recursion vs Iteration
Property
Recursion
Iteration
Definition
A program is recursive when a function calls itself repeatedly until a base condition is met.
A program is iterative if a set of instructions is executed repeatedly using a loop.
Infinite recursion
Infinite recursion can lead to a system crash. Infinite recursion can occur due to a mistake in specifying the base condition.
In an iterative process, the program stops when the memory is exhausted.
Code size
Smaller code size
Larger code size
Time and space
Calling a function each time adds a layer to the stack. Performing the push and pop operation in stack memory makes recursion expensive in both processor time and as well as memory space.
No stack is required in the case of an iterative solution. Hence, an iterative process is a time and space-efficient as compared to the recursive process.
Termination
A recursive code terminates when a base condition is met.
A control variable decides the termination of an iterative process.
Types of Recursion
Recursion can be broadly classified into two types.
Direct Recursion
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
Head Recursion:
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.
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.
Popular recursion examples
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 numberx, when x is raised to the power of n, we multiply xwith 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 ofexp 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.
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.
Base condition: If the value of n is equal to 0, return 0.
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.
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)
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.
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.
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.
Directory Before executing the codeDirectory after executing the code
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))
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
content = io.BytesIO(z.read(f))
zip_file = zipfile.ZipFile(content)
for i in zip_file.namelist():
zip_file.extract_zipfile(i, dirname)
extract_zipfile("PassportManagement_Template.zip")
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)
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.
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))
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.
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
madam is a palindrome!
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.
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.
