Understanding Recursion In Python

Photo by Jesus Kiteque on Unsplash

What is Recursion?

Recursion is a technique where functions or methods makes a call to itself.

Let’s have a look of template of recursive function

Recursion Template

Let’s have an example on the basis of above template

Recursion Example

Difference Between Recursive and Iterative Functions:

Iterative functions use loop and Recursive functions will call functions itself. Let’s have an example:

Iterative Function

In above program we are using while loop which will take (n+1) times and other statements are primitive statements which will execute for constants time.So that whole function will take O(n+1) == O(n) time.

Recursive Function

We can analyse the time complexity of Recursive functions using Recurrence relation.

Recurrence Relation

Recurrence Relation

Types Of Recursion

There are several types of recursion:

• Tail Recursion : When a function call itself and called function is last statement then it is called as a tail recursion.

Tail Recursion

• Head Recursion : When a function call itself and called function is first statement then it is called head recursion.There should not be any statement before recursive call.

Head Recursion

• Tree Recursion : When a function called itself more than once then such type of recursion is known as tree recursion.

Tree Recursion

• Indirect Recursion: In Indirect recursion we will have more than one function and these functions will be calling others functions in a loop or circular pattern.

Indirect Recursion

This blog will give you depth understanding of Recursion . Please give it a try and let me share your feedback.

Thank you for reading :)