Python Recursion
In this post we will cover Recursion in Python. You can watch our videos on Recursion in Python – Click Here
Q. 1 What is Recursion?
Ans. Recursion refers to a programming technique in which a function calls itself either directly or indirectly
A function is said to be Recursive function if it calls itself.
Q.2 Write a Recursive Function?
Ans. Every Recursive function must have at least two cases
The Recursive Case( or the inductive case)-Every recursive function consists of one or more base case and a general, recursive case
The Base Case( or the stopping case)- it causes the recursion to end. Solution is pre-known either as a value or Formula and used directly. The Base Case in a recursive program must be reachable
| Name | Recursion | Iteration |
| Definition | Function calls itself. | A set of instructions repeatedly executed. |
| Application | For functions. | For loops. |
| Termination | Through base case, where there will be no function call. | When the termination condition for the iterator ceases to be satisfied. |
| Usage | Used when code size needs to be small, and time complexity is not an issue. | Used when time complexity needs to be balanced against an expanded code size. |
| Code Size | Smaller code size | Larger Code Size. |
| Time Complexity | Very high(generally exponential) time complexity. | Relatively lower time complexity(generally polynomial-logarithmic). |
Q. 3 Why is base case so important in a recursive function?
Ans. The base case, in a recursive case, represents pre-known case whose solution is also pre-known.
This case is very important because upon reaching at base case, the termination of recursive function occurs as base case does not invoke the function again, rather it returns a pre-known result. In the absence of base case, the recursive function executes endlessly. Therefore, the execution of base case is necessary for the termination of the recursive function.
Q.4 When does infinite recursion occur?
Ans. Infinite recursion is when a recursive function executes itself again and again, endlessly. This happens when either the base case is missing or it is not reachable
Q. 5 What is base case?
Ans. The base case or terminal condition is used to stop recursion.
Q. 6 What is the basic operation principle behind recursion?
Ans. Recursion works on the principle of LIFO(Last in first out)
Q. 7 Which data structure is used to implement recursion? Why?
Ans. Stacks are used to implement recursion as they work on LIFO(last in first out)
Q. 8 What is sys-getrecursionlimit?
Ans. This function is used get the limit of recursive function calls that can be made
Q.9 What is sys-setrecursionlimit?
Ans. This function is used set the limit of recursive function calls
Q. 10 What will happen if no base case is specified in a recursive function?
Ans. The function will endlessly call itself and a stack overflow error will occur
