Many a times we are faced with challenges of writing medium to complex solutions using many level of iterations.We choose to write iterations of loops to meet our foreseen requirements. But the programmer by now would have already heard his inner voice asking “What if n+1 iteration is required”
Then we calm ourselves down saying, we will see when requirement is presented, we shall add another loop to meet it. How about, instead we explore a solution which meets any N iterations and fixes once for all. That’s what we call recursion.
If we inculcate Recursion in Daily useage, this is how it would sound
A child couldn’t sleep, so her mother told her a story about a little frog,
who couldn’t sleep, so the frog’s mother told her a story about a little bear,
who couldn’t sleep, so the bear’s mother told her a story about a little rabbit…
who fell asleep.
…and the little bear fell asleep;
…and the little frog fell asleep;
…and the child fell asleep.
Recursion is event which occurs Periodically, can be instantiated and controlled
The process in which a function calls itself directly or indirectly. corresponding function is called as recursive function.
The solution to base case is provided and solution of bigger problem is expressed in terms of smaller problems.In Our engineering we all have written some basic solutions to problems, be it the Factorial or fibonacci series , tree traversal etc.
In the above example, base case for n < = 1 is defined and larger value of number can be solved by converting to smaller one till base case is reached.
As defined , when a function calls itself, the memory is allocated in stack space of memory allocator. And when the code is not terminated properly then leads to stack overflow exception. Leading to full consumption of stack part of memory.
Hence most important part of recursion is the exit condition. Missing this would end up in a continuous loop, which then will be broken by stack overflow exception.
If fact(10) is called,
it will call fact(9),
it will call fact(8),
it will call fact(7) ….and so on but number will never reach 100.
So, the base case is not reached.
One Classic example of Recursion is Sierpinski Triangle
Direct and Indirect recursion?
A function xyz() is called direct recursive if it calls the same function xyz().
A function xyz() is called indirect recursive, if it calls another function say abc() and abc() calls xyz() directly or indirectly
When to Use and When not to Use
Recursion decreases the readability and debugging becomes difficult. A small code mistake can lead to much larger effect. As everything is multi folded.
Above mentioned factorial can also be solved by simple one level of iteration
People do prefer readability over complexity. Hence recursion should always be used, when it is absolutely required and not to solve simple problems, especially not to solve series problem like factorial or fibonacci
A common table expression (CTE) provides the significant advantage of being able to reference itself, thereby creating a recursive CTE. A recursive CTE is one in which an initial CTE is repeatedly executed to return subsets of data until the complete result set is obtained.
A recursive CTE can greatly simplify the code required to run a recursive query within a SELECT, INSERT, UPDATE, DELETE, or CREATE VIEW statement.
Best Example of this can be Getting the employee hierarchy in a company
Let’s Say we have a table Employees.
Inference:Guy with Manger Id null is the top in hierarchy
Rest of the members we will derive the information using the query
Putting this in a CTE
With Procedure or Function.
Quite a while ago, i was working on a BPSE Deletion, which requires a set of recursive deletion. Idea was to get as much data deleted from foreign key references and then hard code the leaf node deletion.
First step was to form a tree structure of Foreign key references and to do that i had used a procedure , which keeps calling itself until it reaches the leaf node.
This ensured me of forming a tree structure with decisive node level as input. Then one more recursive code which would call this procedure and delete the data.
C# Recursion Code.
I had to work on a functionality to check if the account is already linked in some other businessprofile , before allowing it to be linked in the current businessProfile.
adwordsAdAccount.CanManageClients this is the boolean variable which helps to determine whether the accounts have nesting structure.
Both canManageClients boolean and foreach (var adwordsAdAccount in adwordsAccounts) Served as exit condition here.
Once the accounts structure is rendered , i had to display them in the Select2 drop down, earlier we had 3 level loop structure , which was replaced with indirect recursion.
Input is an object which has accounts in nested format Output is an empty array
Tree View Component Rendering With VueJs
For any tree related operation, Recursion is the answer one will use.
Rendering the structure.
Parent->Children-> Each child has -> Children-> ……..
We wanted to display the structure with UL and LI elements.
html code is
Now that we have gone through the concept of recursion, when to use and when not to use. Possible hiccups if decided to use. Possible use cases of recursions with examples. Power of recursive solutions , we are in better position to expore recursion as a possible solution
With your next code, keep in mind that recursion could be your solution. But then with "Great power comes great responsibility", don’t mess it Up.