Learning Recursion in Python

Introduction

In Computer Science, recursion is a method of finding a solution to a bigger problem by using the solution of smaller subproblems of the same problem. It means that we divide much more complicated problems into one or simpler pieces, after that solving them and using their solution to get the solution of that complicated problem by assembling them in a collective manner.

It means that the final step is reached when some basic condition is satisfied. The Solution for each step is used to solve the previous step and solution for all the steps together from the solution to the whole problem. So when the sub-problems are instances of the original problem, this technique is called recursion.

So, we have to use recursion only if the problem can be divided into smaller subproblems otherwise we have to consider alternatives. When we talk about coding a problem in the programming aspects then this is the way through which “function call itself one or more times in its body either directly or indirectly” and in the response of that call it returns the “return value” of that function call.

Example:- The most popular example of recursion which we could easily understand is the factorial of a number, some other examples of this is the Tower of Hanoi Problem and The Nth stair Problem.

Recursive Function in Python:

The recursive function does not use any special syntax in Python, but it do require some care to define them correctly. One way to describe repetition in python is by using its while-loop and for-loop constructs and recursion is an entirely different way to achieve repetition. As we know in python a function can call other functions So Here It is even possible that a function call to itself
during execution and in response to that call they returning the return value.

Recursive function in Python be like:

When we used mathematics in Computer Science we encountered with the factorial of a number which is:-

As we know that the factorial of any number is the product of all integers from that number upto1.

Example of Recursive function:

1. The factorial Problem
   Example:- when we try to find the factorial of 6 which is denoted as 6!
   It is nothingbut 6!= 65432*1=720

Here factorial( ) is a recursive function in which we enter input as x=3

So, the whole procedure like:-
Factorial(3)
3factorial(2) 32factorial(1)
321
3*2
6

Here 6 is the value which we could find after entering our input as x=3. Behind this whole procedure, each recursive call adds a stack frame to the call stack until we reach the base cases. Then, the stack begins to unwind as each call returns its results. As such a process would repeat indefinitely if they are not stopped by some cases and such cases are known as Base cases. In every recursive program, it must have a base case otherwise the program will continue to execute forever as an infinite loop and StackOverflow may arise.

In our case recursion ends when number reduces to 1, So, Here factorial( 1) is a base case for which we already know the value of factorial. The base case is defined in the body of a function. The cases where n>1 are called recursive cases and when n<=1 we have our base cases.

One more cases arises when we talk about recursive function is recursive case
which is nothingbut the rules which satisfy the criteriaof recursive function.

2.Tower of Hanoi Problem
In this problem, we can only go through a basic theoretical approach to understand how we can solve it using recursion. As there are three posts and n concentric disks shaped like a pyramid, our the main goal is to move n disk from post-A to post C using post-B, following
these three rules:-

• We can move only one disk at a time.
• A disk may not be “set aside”.It may only be stacked on one of the
  three posts.
• A larger disk may never be placed on top of smaller ones.

Problem Solution:-

• Create function Hanoi that takes the number of disks n and the names of the source, Auxiliary and target posts as arguments.
• Move n-1 disks from source post to auxiliary post using the target post as the auxiliary
• Move the remaining diskon the source to the target.
• Move the n-1 disks on the auxiliary port to the target post using the source post as auxiliary.
• For easiness the source post, auxiliary post and target post is
  treated as A, B and C respectively.

What should the base case be?

Here the base case is when the number of disks is 1, in this case, we can simply move one diskfrom A to B and return.

Strategy for solving Recursive Problem:

The strategy for solving a recursive problem is that first, we have to think about the smallest size of problems and write down their solution that is nothing but abase case, now when we solved the base case then we go through the recursive case and at last we have to assemble all these smaller cases to solve the bigger cases so combining both of the base case and recursive cases we got the solution of our original problems which may have of any size.

Benefits of using Recursion:

• By using recursion in our code we can make our program clean and elegant.
• Hereby using recursion, we can solve the more and more complex programs by broken down into simpler subproblems and finding the solution of them through which collectively we solve whole the task.
• In Recursion, It takes fewer lines of code to solve a problem.
• One thing that is easier, by using recursion is that sequence generation other than using some nested iteration

Drawbacks of using Recursion:

• Sometimes it is hard to follow the logic behind the recursion as not all the problems can be solved using recursion.
• Here, If you don’t define the base cases then the code would run infinitely.
• Recursive calls are inefficient as they take up a lot of memory spaces and time.
• They are hard to debug as the function calling itself in a loop and it is hard to understand which call is causing the issue.

Read more about Python, here.

Frequently Asked Questions

Conclusion

So, we can conclude from our above discussion that Recursion is the strongest tool which must have in our Problem-Solving ToolBox. In many cases, it provides us with a natural and elegant solution to the much more complex programs. (Xanax) If the recursive version and loop version to solve a problem are similar we have to prefer our loop version to avoid memory overhead. But even in those cases, recursion offers us a creative way to think about how a problem could be solved.

By Mayank Mishra