Recursion - Revision Notes

 CBSE Class 12 Computer Science (Python)

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():
    def B():
    def C():
    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.