Recursion - Revision Notes
CBSE Class 12 Computer Science (Python)
Recursion
Revision Notes
- Some important points are as follows:
- Recursion refers to a programming technique in which a function calls itself either directly or indirectly. "OR" A function is said to be recursive if it calls itself.
For example:
def A( ):
A( )
Here the Function A () called itself from its own function body, so it is a recursive function, it is the example of direct recursion as the function A() called itself.
another example:
def A():
B()
def B():
C()
def C():
A()
This function is the example of Indirect recursion. - A popular algorithm that uses recursion successfully is binary search algorithm.
- There are two cases in each recursive function, the recursive case and the base case.
- The base case is the case whose solution is pre-known and is used without computation.
- The recursive case is more general case of problem, which is being solved.
- An infinite recursion is when a recursive function calls itself endlessly.
- If there is no base case, or if the base case is never executed, infinite recursion occurs.
- Iteration uses some memory space for each pass contrary to recursion where fresh memory is allocated for each successive call.
- Recursive functions are relatively slower than their iterative counterparts.
- Some commonly used recursive algorithm are factorial, gcd, fibonacci series printing, binary search etc.
- Binary search can work for only sorted arrays whereas linear search can work for both sorted as well as unsorted arrays.