Python Recursive Functions

A Recursive Function is defined as a function that calls itself to solve a smaller version of its task until a final call is made which doesn’t require a call to itself. Each recursive function has two major cases:

  • Base Case
  • Recursive Case
  • Base Case:

    This problem is simple enough to be solved directly without making any further calls to the same function.

    Recursive Case:

    This problem has three steps, the first step at hand is divided into simpler sub-parts. In the second step, the function calls itself but with sub-parts of the problem obtained in the first step. In the third step, the result is obtained by combining the solutions of simpler sub-parts.

    Note: Every recursive function must have at least one base case. Otherwise, the recursive function will generate an infinite sequence of calls thereby resulting in an error condition that is known as an Infinite Stack.

    Program:

    def fact((n):
    if(n==1 or n==0):
    return 1
    else:
    return n*fact(n-1)
    n=int (input("Enter the value of n:"))
    print("The factorial of",n,"is",fact(n))
    

    Output:

    Enter the value of n: 5
    The factorial of 5 is 120
    

  • In this program, Base Case is when n=1 because if n=1, the result is known to be 1 as 1!=1.
  • Recursive Case of the factorial will call itself but with a smaller value of n, It has the following syntax:
    factorial(n) = n*factorial(n-1)
    

    Basic Steps of a Recursive Program:

    Step1: Specify the base case which will stop the function from making a call to itself.
    Step2: Check to see whether the current value being processed matches with the value of the base case. If yes, process and return the value.
    Step3: Divide the problem into a smaller or simpler sub-problem.
    Step4: Call the function on the sub-problem.
    Step5: Combine the results of the sub-problems.
    Step6: Return the result of the entire problem.