Recursion
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. Using the recursive algorithms, certain problems can be solved quite easily. Examples of such problems are Towers of Hanoi (TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of Graph, etc.
What is the base condition in recursion?
In the recursive program, the solution to the base case is provided and the solution of the bigger problem is expressed in terms of smaller problems.
def fact(n):
# base case
if (n < = 1)
return 1
else
return n*fact(n-1)
In the above example, base case for n < = 1 is defined and larger value of number can be solved by converting to smaller one till base case is reached.
How memory is allocated to different function calls in recursion?
When any function is called from main(), the memory is allocated to it on the stack. A recursive function calls itself, the memory for a called function is allocated on top of memory allocated to the calling function and a different copy of local variables is created for each function call. When the base case is reached, the function returns its value to the function by whom it is called and memory is de-allocated and the process continues.
Let us take the example of how recursion works by taking a simple function.
# A Python 3 program to
# demonstrate working of
# recursion
def printFun(test):
if (test < 1):
return
else:
print(test, end=" ")
printFun(test-1) # statement 2
print(test, end=" ")
return
# Driver Code
test = 3
printFun(test)
Output
3 2 1 1 2 3
The memory stack has been shown in below diagram.
More articles on Recursion
- Recursion
- Recursion in Python
- Practice Questions for Recursion | Set 1
- Practice Questions for Recursion | Set 2
- Practice Questions for Recursion | Set 3
- Practice Questions for Recursion | Set 4
- Practice Questions for Recursion | Set 5
- Practice Questions for Recursion | Set 6
- Practice Questions for Recursion | Set 7
Learn DSA with Python | Python Data Structures and Algorithms
This tutorial is a beginner-friendly guide for learning data structures and algorithms using Python. In this article, we will discuss the in-built data structures such as lists, tuples, dictionaries, etc, and some user-defined data structures such as linked lists, trees, graphs, etc, and traversal as well as searching and sorting algorithms with the help of good and well-explained examples and practice questions.
Contact Us