In Python, 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 does not require a call to itself. Every recursive solution has two major cases, which are as follows:
- the base case, in which the problem is simple enough to be solved directly without making further calls to the same function.
- Recursive case, in which first the problem at hand is divided into simpler sub-parts. Second, the function calls itself but with sub-parts of the problem obtained in the first step. Third, the result is obtained by combining the solutions of simpler sub-parts.
Thus, we see that recursion utilized a divide and conquer technique of problem-solving. The divide and conquer technique is a method of solving a given problem by dividing it into two or more smaller instances. Each of these smaller instances is recursively solved, and the solutions are combined to produce a solution for the original problem. Recursion is used for defining large and complex problems in terms of a smaller and more easily solvable problem. In a recursive function, a complicated problem is defined in terms of simpler problems, and the simplest problem is given explicitly.
def fact(n): if(n<=1): return(1) else: return(n*fact(n-1)) number=int(input("Enter the value of number=")) Factorial=fact(number) print("The factorial of ",number," is",Factorial)
Enter the value of number=5 The factorial of 5 is 120
def GCD(x,y): rem=x%y if(rem==0): return(y) else: return(GCD(y,rem)) m=int(input("Enter the value of m=")) n=int(input("Enter the value of n=")) print("The GCD of ",m,"and",n," is",GCD(m,n))
Enter the value of m=8 Enter the value of n=4 The GCD of 8 and 4 is 4
def fibonacci(n): if(n<2): return(1); else: return(fibonacci(n-1)+fibonacci(n-2)) m=int(input("Enter the value of m=")) for i in range(m): print("Fibonacci(",i,") = ",fibonacci(i))
Enter the value of m=6 Fibonacci( 0 ) = 1 Fibonacci( 1 ) = 1 Fibonacci( 2 ) = 2 Fibonacci( 3 ) = 3 Fibonacci( 4 ) = 5 Fibonacci( 5 ) = 8