RECURSION & IT'S TYPES IN PYTHON

?? Hey There !! In This Article It's Time to Learn A New Data Structures Concept which is RECURSION.

???To implement this Practical we will be using Anaconda Python which you can download by Clicking?Here?and from Anaconda Python we will use Jupyter Notebook.

?? Let's Begin.

-----------------------------------------------------------------------------

? What is Recursion ?

?? The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function. Using recursive algorithm, certain problems like Inorder/Preorder/Postorder Tree Traversals can be solved quite easily. Examples of such problems are etc. You can See Recursion the Way Below Image is Repeating :

?? Let's Understand this More Clearly with an Example :

?? This is a Simple Program to Print factorial of 5 Numbers :

?? In the above Program, we've used a For Loop to Print Factorial of 5 which is 5 x 4 x 3 x 2 x 1 = 120. Now if we Use Recursion for Same Output, This is how the code looks like :

?? Let's Understand How this Works :

?? In the For Loop, We give a Base Condition to Enter/Execute The Block of Code inside for loop & i.e for i in range(n) So that the Loop Stops at Certain Point & Doesn't go on Iterating Continuously.

?? Similarly Here, we will First Give a Basic Condition, i.e an if & else Condition. If the Condition Satisfies, then the Recursion will Continue.

?? As you can see Here, the Base Condition is if ( n<=1 ): i.e if the user inputs 0 or 1, then obviously the Factorials will be the Numbers. But if the Number is Greater than 1. Then the Else: Statement have an Important Role .

?? The Else Condition is : n*fact(n-1). Means if n = 5, then according to the condition, 5 x "Again calling the Same Function but this Time Argument is n-1 = 5 - 1 = 4.

5 * fac(4)

?? Now 5 is a Separate Digit. We have n =4 i.e fac(4). The Same else condition which took Place when n = 5 will repeat for n = 4, then according to the condition, 4 x "Again calling the Same Function but this Time Argument is n-1 = 4 - 1 = 3.

5 * 4 * fac(3)

?? n = 3 i.e fac(3) from above Condition. The Same else condition which took Place when n = 4 will repeat for n = 3, then according to the condition, 3 x "Again calling the Same Function but this Time Argument is n-1 = 3 - 1 = 2.

5 * 4 * 3 * fac(2)

?? n = 2 i.e fac (2) from above Condition. The Same else condition which took Place when n = 3 will repeat for n = 3, then according to the condition, 2 x "Again calling the Same Function but this Time Argument is n-1 = 2 - 1 = 1.

5 * 4 * 3 * 2 *fac(1)

?? Base Condition Satisfied, Now Function will Return 1 since n =1. Now All Together we will have 5 x 4 x 3 x 2 x 1 = 120. Refer the Below Image for The Function Explanation where how to get factorial of 4 in Shown.

?? What if we Don't Give the base Condition of if and Else in the Function before calling Recursion ?

?? It's Says, Frames Repeated & From the Frames, Maximum Recursion Depth Exceeded.

?? Let's Understand This More Clearly.

-----------------------------------------------------------------------------

? What is Stack Frame ?

?? In the Above Block Diagram, You can see that the RAM is Divided into 4 Parts when it Comes to Compiling and Running the Program.

?? Let's understand with the Help of an Example that How This Memory Work :

?? In the Above Example, A Simple Code is used where inside a Function, An integer Variable x = 10 is Declared and The value for the same is Printed.

?? Now when the Code is Compiled. It gets Converted into Machine Code and gets Loaded in the Program Code section in the Memory.

?? Above that, Memory will be allocated for all the Variables present in the Code. Which can also be Termed as An Entry Point for the Function inside the Stack Memory

?? When The Part of Variables, in this Case x = 10, which belongs to the void main () Function in the Program code Section is known as Activation Record for that Function. Means x in the print Statement inside The Function will refer to the x = 10 (Activation Records) in the Stack Memory.

-----------------------------------------------------------------------------

?? Note : The Activation Record Gets Created inside the Stack Only when the Function is Called.

-----------------------------------------------------------------------------

?? To Make it more Clear, Have a Look at How the Function Call Works :

?? Looking at the Code, After Compiling, it gets loaded in the Code Section. & we have two Variables This Time Created as Activation Record when the Function is Called.

?? Stack Works on LIFO i.e (LAST IN FIRST OUT) Method And Here you can see in the Stack Memory x = 11 is not yet Terminated, Instead another memory is allocated for a = 11 variable.

?? Every Function that Runs in the Code access the Top Most Data Element From the Memory.

?? In the above Code inside the main () Function, A(x) means the A() function is Called with x as an argument and it will access the First Data Element i.e a = 11 as shown in the Diagram Above.

-----------------------------------------------------------------------------

?? So From the Example, it is Clear That The Data Elements Get stored as Activation Record on top of Other For each Function. That Means n Functions = n Activation Records

?? So if we Come back to the Example of Recursion for Factorial :

?? If we Don't Give The Base Condition. The Call Stacks will Keep on Continuing Until it Captures the Whole Memory Available for Code. Hence after certain point of time, when the Whole available memory is Used, it will Exceed and Hence the Program Crashes. Thus Giving Base Condition is Important.

-----------------------------------------------------------------------------

? Types of Recursion :

?? There are 4 Types of Recursion :

• Direct Recursion
• Indirect recursion
• Tail recursion
• Head / Non-Tail Recursion

??Let's have a Look at an Example for Each :

-----------------------------------------------------------------------------

?? Direct Recursion :

?? A Recursion in Which the Function calls the Same Function again is known as Direct Recursion.

??Example :

?? Above is the example for Direct Recursion but Just to Avoid the Stack Overflow we Are Giving the if Else Condition.

-----------------------------------------------------------------------------

?? In-Direct Recursion :

?? ?If?function function1() calls another function function2() and function2() eventually calls the original function function1() is known as In-Direct Recursion.

?? In the Below Program, We have to Print 1 to 10 numbers in Such a Way that if the number is odd, then add 1 and if it's even, then subtract 1.

?? Initially the variable n is declared with value as 1, so from the Question we have to add 1 if the number is odd.

?? Below that an Odd Function is Created with an Argument of the variable n itself.

?? Here as the number is odd, thus we will Print the number by Incrementing it by 1 which will be 2 and will update the value in the same variable.

?? From the Definition of tail Recursion, We will now call another/Different Function which is Even and will pass the Same Argument.

?? Now the Number 2 will Go to the even Function and Again the Condition Gets Satisfied .The even Number gets Decreased by 1 and after Subtracting, we will Increase the Value by +1 since we have to Move Forward in Digits. And Then The Argument which odd Function will have is 3

?? This Cycle keeps on Repeating until the number Becomes Greater than 10 & The Output is :

?? Main Point to be Noted Here is The Way Indirect Recursion Works :

-----------------------------------------------------------------------------

?? Tail Recursion :

?? The Recursion in which the Function inside the Function is Called at the Last of all the Statements is known as Tail Recursion.

?? We've Already the Discussed about the Tail Recursion in the Program to Find Factorial for First Five Numbers. Here's Another Simple Program to Print first 3 Numbers in Reverse order (3,2,1).

?? Nothing very Complex, Just an if Condition and a Tail Recursion at the Last.

-----------------------------------------------------------------------------

?? Head / Non-Tail Recursion :

?? This is Exactly Opposite to The Tail Recursion

?? The Recursion in which the Function inside the Function is Called Before the Statements are executed is known as Head or Non-Tail Recursion.

?? Just a Small Change in the Above Program can Lead us to Non-Tail Recursion.

-----------------------------------------------------------------------------

???So From the Above Article we Saw How to Implement Recursion in Python. If you Find This Interesting then Do Follow & Connect???.

THANK YOU !!

-----------------------------------------------------------------------------