Base Case in Recursive function python

In this article, we will learn about Python's base case in a recursive function.

Before learning this, let’s first understand what recursion is in Python and the use of recursion in Python.

What is Recursion in Python?

Defining something in terms of another object is known as recursion. A concrete example would be to align two parallel mirrors to face one another, and any object in their path would be recursively mirrored. This can allow you to loop through data to conclude.

Recursion is a computational technique for solving problems in computer science where the answer depends on answers to smaller versions of the same question. It uses functions that call themselves from within its code to deal with such recursive issues. The approach can be applied to a variety of problems.

Recursive Function in Python

Recursive functions recall themselves, as implied by the word "recursive." As a result, the identity function is invoked once or more.

The winding and unwinding phases are the two separate working phases of all recursive functions. The first call to the recursive function initiates the winding phase, which continues until the last call.

The syntax of the recursive function is given below:

Let’s understand recursion by taking an example given below:

Example

#defining a function as greet
def greet(n: int):
   if n == 0:
       return
   # recursive call
   greet(n - 1)
#print hello world
   print("Hello world!")


# function call
greet(5)

Output

In the above example, we are printing Hello world! Five times using recursion.

So firstly, we create a function name as greet and pass parameter n in it.

Then check if n == 0, then return again and else n is not 0 then print hello world n-1 times bu recursive call and for printing Hello world we should call the function as greet() and put in this the no that how many times we want to print this.

In this way, we print 5 times. Hello world! By using a recursive call.

Use of Recursion in Python

When problems may be divided into simpler components for faster computation and more understandable code, recursion is used in Python.

There are two options, for example, if you look up a student in a school. You may assemble the pupils in a large auditorium and go through each individually looking for her. It would make more sense to first look for the grade she is in, then the class, and then you'll be able to identify her location much more quickly.

A simpler technique would divide the school into sections until the smallest section could be created to find the kid. Recursion can increase memory use even if it has been shown in some circumstances to produce results more quickly when correctly optimized.

NOTE: Therefore, recursion should only be used when necessary.

The following two essential parts must be considered before writing any recursive functions:

• Recursive case
• Base case

Recursive Case in Python

A recursive case should be included in a recursive function, calling the recursive function with input to move it closer to its base case.

The use of a call stack is a feature of recursive functions, and the recursive function is added to the top of this stack each time it is invoked. Imagine cutting open an onion and placing each layer you remove close to it. Each layer would then be peeled and stacked on top of one another, and this is now put up against a recursive function.

A recursive function call would be required to peel each layer. The first peel() would be inserted at the top of the stack once the first layer is peeled, followed by the next peel() above it, and so on until the process is finished.

Base Case in Python

The simplest example that must be considered when solving a problem is the Base Case, which also results in the termination

 of the recursion.

When the recursive function should stop, it is determined by the base case. The base case and its solution must be found first to create a recursive function.

Depending on many factors, more than one base case can be used. Once a base case has been determined, it is necessary to decide on the general or recursive case such that each call advances us closer to obtaining the base case.

Below is the syntax of recursive case and base case in Python:

def recursive_function_name():
if(condition)                       # base case
      	 #This is a simple statement without recursion


else                                # recursive case
      	 This statement is calling recursive_function_name()

Note: If your function doesn't have a base case, it calls itself infinite times and might use all of your memory for the recursive stack.

Let’s understand it by taking an example given below:

Example

#defining a function name as factorial() with parameter n
def factorial(n: int):
   ans = n
   ans *= factorial(n-1)
   return ans


#prints factorial of 5 as output
print("factorial of 5 is", factorial(5))

Output

RecursionError: maximum recursion depth exceeded

In the above example, we do not have any base case. We can see the factorial() function is called till there is memory in the stack, but we didn’t get any answer.

In order to obtain the desired outcome, it is advisable to employ a base case and be pretty intuitive.

Generally, the base case is decided by keeping in mind what can be the smallest input and what will be the output for that input.

In the above example, the smallest inputs may be 1 or 0. For these inputs, the function should return 1 because the factorial of 1 and 0 will be 1.

#defining a function name as factorial() with parameter n
def factorial(n: int):
   ans = n
   if n <= 1: #base case
       return 1
   else:
       ans *= factorial(n-1)
   return ans


#prints factorial of 5 as output
print(factorial(5))

Output

120

In the above example, we have a base case when the value of n is less than or equal to 1, and then our factorial function will return 1.

In the above example, we are calculating the factorial of 5. So we have called factorial function with parameter value 5. 5 is not less than or equal to 1, so it will go in else part. Here ans having value 5 will be multiplied by the factorial of 4.

That will be factorial of 5, and then ans should be returned. But factorial (4) value is unknown, so it will calculate it the same way as the computed factorial of 5 (i.e. factorial of 4 = 4 * factorial of 3) and so on. As the value of n will be 1 function will return 1. Now we have the value of factorial 1, so the function can calculate the value of factorial 2 and then the value of factorial 3 and so on, and now it will return the value of factorial 5, which will be 120.

Let’s take one more example better to understand a base case in Python's recursion.

Example

#defining a function name as gcd() with parameters a and b
def gcd(a,b):
   if b== 0:    #base case
        return a
#recursive case
   return gcd (b,a%b)
#prints gcd of 100 and 200 as output
print(gcd(100,200))

Output

100

We can calculate the GCD of two numbers by using recursion in Python.

The above example holds GCD of a and b. If a>b, then GCD is the same as gcd (b,a%d).

The base case in the above example is when b==0 as gcd (a, 0) is a. Observe that the second input strictly reduces in each recursive iteration since a % b <b to show that the reduction step converges to the base case. 

The first recursive call switches arguments if a>b.

Conclusion

We deal with a counter or a Boolean variable with an iterative approach. If it is true, then we iterate in a loop, and when the condition becomes false, we come out of the loop.

In recursion, this concept is known as the base condition. It is the end of the recursion. The base case determines whether the recursive function will call itself or it will return. Without the base case writing a recursive function is similar to writing an infinite loop.

Your computer will display an error due to a stack overflow since we utilize a call stack to keep track of the function calls if the base case is insufficient.