Recursive Function Python

Hi guys, welcome to this post entitled “Recursive Function Python”. So basically we are going to learn how do we use Recursion with Python Programming Language. Recursive function is very useful in programming languages. Almost all programming languages support Recursive function. It is a powerful and wonderful tool to solve complicated problems.

So let’s start the obvious question – What is Recursion?

What is Recursion?

We all are familiar with recursion as we have learned it in many programming languages. But just now i am defining it in general terms. Later I will discuss it with respect to python.

Recursion is a process such that each term is generated by repeating a particular mathematical operation.
It is the act or process of returning or running back.
Recursion is a kind of problem solving methods that break the problems into smaller problems.
It was originated from Latin word “recursionem” that means “a running backward, return,”.

Recursion In Nature

Here i am showing few examples of recursion that are found in nature.

This type of things are really very amazing.

Real World Example Of Recursion

Before proceeding ahead we take an example from real world.That will explain the recursion very well.There are many examples around us which shows the concept of recursion. But generally,we don’t care about them.So next time if you face them then carefully observe them. I am taking one example which you all have already seen.

Have you ever gone to the beauty parlour ?
If yes ,then you might have observed that interesting scene.
when you sit on chair then you see a mirror is in front of you and another is in back to you.
Hence, your image appears on the front mirror. And as a result the image of first mirror reflected into the backside mirror.
And this occurs and occurs infinitely.This phenomena is known as Recursion.
This is very amazing thing.And yes i like and enjoy it very much.So, i hope next time you will also enjoy it.

Furthermore I am going to explain Recursive Function in Python. So let’s start without wasting time.

In python, we already familiar that a function can call another function. There is also a possibility that a function can call itself. This is referred to as recursive function.

Recursive function yields a solution by reducing the problem to smaller and smaller version of itself.
It is processed until you reach a base case or a problem which always can be solved easily.

Also Read – Python Lambda Function Tutorial – Working with Lambda Functions

Devising A Recursive Solution

A recursive function can go infinite like loops. To avoid this situation recursive function must have the following rules –

Identify a base case that is easily solvable.
Identify a recursive case that breaks the problem into smaller problem of the same form.

Base case

It is the case in recursion where the answer is known, or we can say the termination condition for a recursion to unwind back. There’s no standard in the base case, any input that is simple enough to be solved exactly can be chosen as one.

Recursive case

It is the case which brings us to the closer answer.

General Structure Of A Recursive Function


if(base case condition)
    //Calculate base case without recursion
else 
    // recursive case

if(base case condition)

//Calculate base case without recursion

else

// recursive case

Break the problem down into a smaller problem of the same form.
Solve the smaller problems by calling the recursive function.
Smaller solutions can be used to solve the larger problem.

Classic Example Of Recursive Function

Now i am taking a most common example of recursive function that is Factorial of a number. You can read more about factorial on factorial. The usual definition of “n factorial” is “n! = n * (n – 1) * (n – 2) *…* 2 * 1,” where ‘n’ is a positive integer.


def fact(n):
    if n==0 :
        return 1
    else:
        return n*fact(n-1)

n = int(input("enter the number :"))
result = fact(n)
print("Factorial of",n,"is",result)

def fact(n):

if n==0 :

return 1

else:

return n*fact(n-1)

n = int(input("enter the number :"))

result = fact(n)

print("Factorial of",n,"is",result)

Description Of Code

Now i am going to explain what i have done in the above code –

First of all we need to define a function , it takes an argument.
Inside this function body implement if-else condition.
Here if part contain the base case and else part contain the recursive case.
Now, first we check whether the entered number is equals to 0.If this is true then return 1 because value of 0 is one.And this is our base condition.
Next if the entered input is greater than 0 then return recursive condition i.e., n*fact(n-1) .
Next, outside the function body ask user to enter the input.
Then call the function.
And at last print the result of factorial of entered number.

Now run the code,the output will be as below –

Function Calls

Let’s understand how function call is happening.

In the above example i have entered 5.
So, we will see the function call of 5.
Here Base case is n=0
Recursive case is n!=n*(n-1)!


Function Calls
fact(5)    5*fact(4)                         120
    fact(4)      4*fact(3)                    24
        fact(3)       3*fact(2)                6
            fact(2)       2*fact(1)            2
                 fact(1)       1*fact(0)       1
                      fact(0)       return 1   1

Function Calls

fact(5) 5*fact(4) 120

fact(4) 4*fact(3) 24

fact(3) 3*fact(2) 6

fact(2) 2*fact(1) 2

fact(1) 1*fact(0) 1

fact(0) return 1 1

Here the recursive function is breaking down the problem in smaller problem and calling itself for each of the smaller problem.
For getting factorial of 5 is equals to 5 times of getting factorial 4.
For getting factorial of 4 is equals to 4 times of getting factorial 3.
In this way the problem is breaking down into smaller problem.
As a result the function fact() is calling itself in each function call.
So, the recursion is performed in this way.

Why We Use Recursive Function?

A very important question arises “Why We Use Recursive Function?” So, the answer is here. It sometimes makes your code much simpler!

One way to think about recursion:

Whenever we call a recursive function, the function clones itself, making new copies of:
- the code
- the local variables (with their initial values),
- the parameters

Each copy of the code includes a indicator that marks the current position. When a recursive call is made, the indicator in the old copy of the code is just after the call; the indicator in the “cloned” copy is at the beginning of the method.
When the method returns, that clone goes away, but the previous ones are still there, and know what to execute next because their current position in the code was saved (indicated by the indicator).

Pros Of Recursive Function

Less Coding – Recursion is generally known as Smart way to Code.
Time efficient – If you use recursion with memorization, Its really time saving.
Fast and Easy – In some cases, extremely fast and easy to code.
practical – Extremely practical for tree traversal and binary search.
Natural Solution – For certain problems the recursive solution is the most natural solution.
Easier to reason – Recursive solutions are easier to reason about

Cons Of Recursive Functions

Often harder to debug.
Slows down processing time.
Does not scale up like iteration ,requires more memory.
Sometimes more abstract or harder to understand than iterative solutions.

So, that’s all for this Recursive Function Python Tutorial friends. Now, I hope you have understand the Recursive Function very well and from now it will not bother you anyway. So friends like this and share this with your friends. Thanks all of you.

Recursive Function Python – Learn Python Recursion with Example

What is Recursion?

Recursion In Nature

Real World Example Of Recursion