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.
Base Condition
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.
int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}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.
Fatal Error
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.
int fact(int n)
{
// wrong base case (will cause stack overflow).
if (n == 100) {
return 1;
}
else {
return n*fact(n-1);
}
} 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().
void xyz()
{
// Some code....
xyz();
// Some code...
}A function xyz() is called indirect recursive, if it calls another function say abc() and abc() calls xyz() directly or indirectly
void xyz()
{
// Some code...
abc();
// Some code...
}
void abc(){
// Some code…
xyz()
// Some code...
}When to Use and When not to Use
Recursion can be used at all places, but that doesn't mean it is a best practice There isn’t any specifics as to use the recursion, it can be used in almost all places, be it the SQL server,C#,Javascript, Vue Component etc. Any repetitive Iterations, recursion could be the alternative.
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
for(int i = 1; i <= n; i++)
{
mul = mul * i;
}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
Database Recursion
With CTE.
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.
EmployeeID smallint NOT NULL,
FirstName nvarchar(30) NOT NULL,
LastName nvarchar(40) NOT NULL,
Title nvarchar(50) NOT NULL,
DeptID smallint NOT NULL,
ManagerID int NULLInference:Guy with Manger Id null is the top in hierarchy
SELECT e.ManagerID, e.EmployeeID, e.Title, edh.DepartmentID, 0 AS Level
WHERE ManagerID IS NULLRest of the members we will derive the information using the query
-- Recursive member definition
SELECT e.ManagerID, e.EmployeeID, e.Title, edh.DepartmentID,
Level + 1
FROM Employees AS ePutting this in a CTE
WITH EmployeeHierarchy(ManagerID, EmployeeID, Title, DeptID, Level)
AS (
SELECT e.ManagerID, e.EmployeeID, e.Title, edh.DepartmentID, 0 AS Level
FROM.Employees AS e
WHERE ManagerID IS NULL
UNION ALL
-- Recursive member definition
SELECT e.ManagerID, e.EmployeeID, e.Title, edh.DepartmentID, Level + 1
FROM.Employees AS e
INNER JOIN EmployeeHierarchy AS d
ON e.ManagerID = d.EmployeeID
)
SELECT ManagerID, EmployeeID, Title, DeptID, Level
FROM EmployeeHierarchyWith 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.
Procedure: usp_formFkTree
Declare @lvl =0
table #tbl
id int identity,
tablename varchar(256),
lvl int,
ParentTable varchar(256);
Declare @hirerachycurS cursor;
if @lvl = 0
insert into #tbl (tablename, lvl, ParentTable)
select @table, @lvl, Null;
else
insert into #tbl (tablename, lvl, ParentTable)
select @table, @lvl,@ParentTable;
if not exists (select * from sys.foreign_keys where referenced_object_id = object_id(@table))
Return; --exit condition
else
begin -- else
set @ParentTable = @table;
set @hirerachycurS = cursor for
select tablename=object_schema_name(parent_object_id)+'.'+object_name(parent_object_id)
from sys.foreign_keys
where referenced_object_id = object_id(@table)
and parent_object_id <> referenced_object_id; -- this to prevent self-referencing which can create a indefinitive loop;
open @hirerachycurS;
fetch next from @hirerachycurS into @table;
while @@fetch_status = 0
begin --while
set @lvl = @lvl+1;
-- recursive call
exec dbo.usp_formFkTree @table, @lvl, @ParentTable, @dbg;
set @lvl = @lvl-1;
fetch next from @hirerachycurS into @table;
end --while
close @hirerachycurS;
deallocate @hirerachycurS;
end -- else
if @lvl = 0
select * from #tbl;
Return;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.
public void CheckAccountsIfAlreadyLinked(IList<AdwordsAdAccount> adwordsAccounts, int businessProfileId)
{
//Some Code
foreach (var adwordsAdAccount in adwordsAccounts)
{
//Some more Code
if (adwordsAdAccount.CanManageClients){
CheckAccountsIfAlreadyLinked(adwordsAdAccount.ChildAccounts, businessProfileId);
}
}
}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.
JS Recursion
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
var recursiveRender = function(input,output){
if (input.ChildAccounts != null && input.ChildAccounts.length > 0) {
var parent = { text: input.Name, children: [] };
output.push(parent);
renderAccounts(input.ChildAccounts, parent.children);
}
else {
output.push({
id: input.Id,
text: input.Name,
disabled: input.BusinessProfileId > 0,
Businessprofilename: input.Businessprofilename,
BusinessProfileId: input.BusinessProfileId
});
}
};
var renderAccounts = function (input, output) {
$.each(input, function (index, item) {
recursiveRender(item, output);
});
};Tree View Component Rendering With VueJs
For any tree related operation, Recursion is the answer one will use.
Rendering the structure.
Let's say we have a javascript object in format
Parent->Children-> Each child has -> Children-> ……..
We wanted to display the structure with UL and LI elements.
html code is
<treeviewcontent :children=”accountCampaigns.children”/>
Vue.component("treeviewcontent",{
props: ["children"]
,template: " <ul>" +
'<li v-show="child.Visible" v-for="child in children">' +
'<input type="checkbox" :id="getuniqueId(child)" :value="child" v-on:change="selectRecursive(child,child.isSelected)" v-model="child.isSelected"/>' +
'<span v-on:click="toggleVisiblity(child)"></span>' +
'<treeviewcontent v-if="child.children" :children="child.children" ></treeviewcontent>' +
"</li>" +
"</ul>"
}
Exit condition here would be
<treeviewcontent v-if="child.children" :children="child.children" ></treeviewcontent>
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.