Python Recursion (Recursive Function) with Examples
The Recursion In Python 3
In this Python Tutorial 2021, you will learn to create a recursive function (a function that calls itself).
You have learnt how to create and invoke methods/functions in Python. Inside the function bodies, we can include function-call of other functions. But have you ever thought : Could a method invoke or call itself ?
Self-invocation may at first sound useless or ill : Isn’t this defining something in terms of itself – what is called circular definition ? But self-invocation is legal, and it’s actually quite useful. In fact, it’s so useful that it gets its own special name : recursion.
What is recursion ?
Recursion refers to a programming technique in which a function calls itself either directly or indirectly.
A Physical word example would be to place two parallel mirrors facing each other. Any object in between them would be reflected recursively.
Python Recursive Function
recursion in python 3
In Python, we know that a function can call other functions. It is even possible for the function to call itself. These types of construct are termed as recursive functions.
The following diagram shows the working of a recursive function called recurse.
Following is a example of a recursive function to find factorial of an integer.
Factorial of a number is the product of all the integers from 1 to that number.
the factorial of 6 (denoted as 6!) is
1*2*3*4*5*6 = 720
Example of a recursive function
program . factorial program in python using recursion ?
def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))
The factorial of 3 is 6
In the above example, factorial( ) is a recursive function as it calls itself.
When we call this function with a positive integer, it will recursively call itself by decreasing the number.
Each function multiplies the number with the factorial of the number below it until is equal to one.
This recursive call canbe explained in following steps.
factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call
let’s look at an image that shows a step-by-step process of what is going on :
You can say that recursion can be :
direct recursion, if a function call itself directly from its function body.
indirect recursion, if a function calls another function, which calls its caller function.
following figure illustrates it.
This section is going to discuss recursion and recursive function. We shall be learning how to write recursive functions and implement recursion. But before we proceed, carefully go through the following code and figure out its output.
def func1( ) print("Hello func2") func2( ) def func2( ) print("Yes func1") func1( )
Yes, you guessed it right. This code will print the following ENDLESSLY :
Hello func2 yes func1 Hello func2 yes func1 :
The above functions (func1( ) and func2( ) ) will keep on calling one another infinitely and the entire memory will be used up – No stop!
Python will report following runtime error for it :
RuntimeError : maximum recursion depth1 exceeded . . .
The problem with above code is that it is a Recursive program but recursion code is NOT SENSIBLE.
You must write a sensible recursive code that has clearly defined ‘where to stop’.
Right or Sensible Recursive code is the one that fulfils following requirements :
- it must have a case, whose result is known or computed without any recursive calling – the BASE CASE. The BASE CASE must be reachable for some arguement/parameter.
- it also have recursive case, where by function calls itself later section.
Program 1. Write a recursive function that computes the sum of numbers 1..n; get the value of last n from user.
# program to illustrate recursion def compute(num) : if(num == 1) : return 1 else : return(num + compute(num - 1)) #_main_ last = 4 ssum = compute(last) print("The sum of the series from 1 ..", last, "is", ssum)
The output produced by above code is :
The sum of the series from 1 .. 4 is 10
Program 2. Write a recursive function to print a string backwards.
def reverse(s): if len(s)==1: return s else: return(s[-1] + reverse(s[0:len(s)-1)) s = input("Enter a string :") print(reverse(s))
Enter a string : abc cba
RECURSION IN PYTHON
As you have seen, recursion occurs when a function calls itself.
In Python, as in other program ramming language that support it,
recursion is used as a form of repetition that does not involve iteration.
A Recursive Definition is a definition that is made in terms of smaller version of itself.
Have a look at following definition of x^n , which is non-recursive :
x^n = x*x* … *x (Iterative definition – non-recursive)
Now, it can be represented in terms of recursive definition as follows :
x^n = x*(xn – 1) for n > 1 (recursive definition)
= x for n = 1
= 1 for n = 0
Writing a Recursive Function. Before you start working recursive functions, you must know that every recursive function must have at least two cases :
(i) the Recursive Case (or the inductive case)
The BASE CASE is a small problems that we know how to solve and is the case that causes the recursion to end.
In other words,
it is the case whose solution is pre-known (either as a value or formula) and used directly.
(ii) the Base Case (or the stopping case) – ALWAYS REQUIRED
The Recursive Case is the more general case of the problem we’re trying to solve using recursive call to same function.
As an example, with the power function x power n, the recursive case would be :
Power(x, n) = x*Power(x, n-1)
and the base cases would be
Power(x, n) = x when n = 1 Power(x, n) = 1 when n = 0
- The Base case in a recursive program MUST BE REACHABLE.
- Every recursive function consists of one or more base cases and a general, recursive case.
Other cases(when n<0) we are ignoring for now for simplicity sake.
Consider the following example() of Power function :
Program 3. Program to show the use of recursion in calculation of power e.g., a^b. (where ^ symbol of power )
# power a to b using recursion def power(a, b) : if b == 0 : # BASE CASE return a*power(a, b-1) #__main__ prin("Enter only the positive number below") num = int(input("Enter base number :")) p = int(input("raised to the power of :")) result = power(num, p) Print(num, "raised to the power of", p, "is", result)
The output produced by above program is as :
Enter only the positive number below Enter base number : 7 raised to the power of : 3 7 raised to the power of 3 is 342
If there is no base case, or if the base case is never executed, an infinite recursion occurs. An Infinite Recursion is when a recursive function calls itself endlessly. Infinite recursion can happen in one of the following cases.
(i) Base Case Not Defined. When the recursive function has no Base Case defined, infinite recursion will occur.
(ii) Base Case Not reached. Sometimes you have written a base case but the condition to execute it, is never satisfied, hence the infinite recursion occur.
- There can be one or more base cases in a recursive code.
- An infinite recursion is when a recursive function calls itself endlessly.
Recursive Binary Search
Now that you have fair idea about Binary search algorithm and how it works, let us see how it can be implemented recursively.
As you can see that process of finding the elements same in all search-segments, only the lower limit low and higher limit high of a segment changes if the element is not found at the middle(mid) position of the search-segment. Thus, a recursive call can be made to the binary search function by changing the limits.
The search stops when either the element is found and its index is returned OR lower limit becomes more than higher limit-this will happen when the search -segment reduces to size of single element and search is still unsuccessful, in this case both mid +1 or mid -1 will make lower limit more than higher limit – which means search is unsuccessful.
Program 4. Write a recursive function to implement binary search algorithm.
#binary recursive search def binsearch(ar, key, low, high) : if low > high : # search unsuccessful return -999 mid = int(low + high)/2) if key == ar[mid] : # if key matches the middle element return mid # then send its index in array elif key < ar[mid] : high = mid - 1 # now the segment should be first half return binsearch(ar, key, low, high) else : low = mid + 1 # now the segment should be latter half return binsearch(ar, key, low, high) #_main_ ary = [12, 15, 21, 25, 28, 32, 33, 36, 43, 45] # sorted array item = int(input("Enter search item :")) res = binsearch(ary, item, 0, len(ary) - 1) if res >= 0 : # if res holds a o .. n value, print(item, "FOUND at index", res) else : print("Sorry!", item, "NOT FOUND in array")
Some sample runs of the above program as shown below :
Enter search item : 32 32 Found at index 5 ========================= Enter search item : 10 Sorry! 10 NOT FOUND in array
- Recursive functions make the code look clean and elegant.
- A complex task can be broken down into simpler sub-problems using recursion.
- Sequence generation is easier with recursion than using some nested iteration.
- Sometimes the logic behind recursion is hard to follow through.
- Recursive calls are expensive (inefficient) as they take up a lot of memory and time.
- Recursive functions are hard to debug.
Recursion VS Iteration
In iteration, the code is executed repeatedly function using the same memory space. That is, the memory space allocated once, is used for each pass of the loop.
On other hand in recursion, since it involves function call overheads, the recursive function runs slower than its iterative counterpart.
Recursion In Python 3
- Recursion allows us to break a large task down to smaller tasks by repeatedly calling itself.
- A recursive function requires a base case to stop execution, and the call to itself which gradually leads to the function to the base case.
- It’s commonly used in trees, but other functions can be written with recursion to provide elegant solutions.
Read More :
Q 1. What is recursion in Python?
ans. Recursion means calling a function in a function, If you want to know more about recursion then go https://kamalsinghstarbooks.xyz/functions‑in‑python/
Q 2. How do you stop a recursive function in python?
ans. Recursion function is stopped by using a base case . Base case is nothing but just a limit to recursion function.
Import sys Print (sys.getrecursionlimit())
Q 3. How does Python recursion work?
ans. A recursive function is a function defined in terms of itself via self-referential expressions.
This means that the function will continue to call itself and repeat its behavior until some condition is met to return a result.
Q 4. Is recursion hard to learn?
ans. It’s a tough book that moves at a fast pace without a lot of hand holding for its problems, but working through it will give you a lot of exposure to recursive thinking and lots of other concepts.
The section that introduces recursive function calls. Yes, it is kind of hard. Don’t be discouraged.
Q 5. How do you read recursion better?
ans. A recursive function is simply a function that calls itself as many times as it needs to do so.
It’s useful if you need to process something multiple times, but you’re unsure how many times will actually be required.
In a way, you could think of a recursive function as a type of loop.
Q 6. Is Python 2 or 3 better?
ans. When it comes to Python 2 vs 3 in 2018, Python 3 is the clear winner. Since Python 2 is being phased out by 2020,
mass Python 3 adoption is the clear direction of the future.
Q 7. What is the use of Python 3?
ans. But over time, I have observed that there are 3 main popular applications for Python: Web Development. Data Science — including machine learning, data analysis, and data visualization. Scripting
Q 8. What is recursion limit?
ans. The recursion limit is there specifically to avoid these types of crashes.
Each recursion doubles the amount of memory that is allocated by the function and a stack is used to store the data.
A stack consists of a limited amount of memory and when this limit
is reached, the program cannot keep running.
Q 9. How do you clear recursion limits in Python?
ans. The Python interpreter limits the recursion limit so that infinite recursions are avoided. The “ sys ” module in Python provides a function called setrecursionlimit() to modify the recursion limit in Python. It takes one parameter, the value of the new recursion limit. By default, this value is usually 10^4.