Recursive way of Iteration
(We’re going to talk about problem solving in a recursive approach and it’s visualisation.
More to cover after briefing:
like examples, about trade-offs, it’s compatibility with old iterative way and much more…)
So, What is recursion ?
Recursion is a statement that calls the same method declaration with same amount of parameters to achieve certain outcome. Formally the definition of recursion is “A common method of simplification is to divide a problem into sub-problems of the same type”. Recursive functions uses internally something called The call stack. When a program calls a function, that function goes on top of the call stack.
Before proceeding…
Truth is recursion is not that much easier to break-up the visualization in mind.
And it’s not a big deal if we learn to think from bottom up approach, means that we shall start thinking from result perspective — (outcome after proper termination to be precise). As decomposition of code block is very tough based on types of recursions, imagining is up to your use case & thinking.
words like def, function, method, block are interchangeably used in this blog. code-snippets are mostly from java, scala, python..
Let’s start:
Getting into it.. The Execution flow starts with exit condition check and continues its calling to itself with same amount of params, with reduced parameter values (most of the times). Probably one or more statements of the function will points to the same function
What some geeks says about recursion?
Recursion method will have many copies. Each copy has it’s own method definition that calls with the same number of parameters and decreased/increased values.
Multiple recursion is a kind of expanded n-ary tree each node of sequentially modified parameter value until leaf node except leaf node (as it’s exit condition).
Explanation…
As you seen from left side image control is moving towards down and after getting incurred to non-recursive call (the exit condition) computation will be started from top & continues up to popping up the last calls until stack becomes empty. then value gets back to previous recursive statement (towards up). The left side pic is about linear recursion. Let’s get into examples..
from above pic we’ve seen how a simple recursive function grows like stack.
Examples — Let’s get started with simple example
Let’s discuss about types:
There are different types in recursion?. Yes, We are going to discuss various types of recursions with examples. [Content to be covered with Linear, Tail, Binary, Multiple recursions.]
- Get Ancestors of a tree (structure) :-
2. count vowels
more examples are at down 👇 (As towers-of-honoi we already know, will hop it)
Different types in recursion:
Linear recursion:
Linear recursion is generally normal recursion.
That calls to itself each time when function runs (as opposed to one that would call itself multiple times during its execution). Factorial is a good example for that.
Direct Recursion:
Direct recursion or popularly named head recursion. its functionality is to compute results using recursion and final calculations among the outcome and then return it to callee function.
Tail Recursion:
Tail Recursion is most efficient way to get the output to the current iteration from sub problem which is already computed and stored to use it further. I am gonna write a separate notes for tail recursion. Please stay tuned.
Binary Recursion:
Binary recursion is much faster than normal recursion. As we trigger same function call more than once to compute with faster times.
Best ever example is we know it very popularly. i.e factorial => if n>2 : fib(n) = fib(n-1)+fib(n-2)
Nested Recursion:
Nested recursion is a bit harder algorithm that can rarely hit us on the field.
But it is not supposed to use for faster computations. It will lead to an exponential timing depends on the algorithm we used.
And it is also very typical to get visualized view of the same.
Mutual Recursion:
Mutual recursion is as name tells us to call between two methods each other to get the result.
as above example computes every number is odd or even until it comes to number zero.
Generative Recursion vs Structural Recursion?
The key difference between structural and generative recursion is where a recursive procedure gets the data that it works on and how it processes that data. Specifically, for structural recursion, a recursive call is made on a subset of the original input data. Whereas for generative recursion, a recursive call is made on data that was constructed/calculated from the original input data.
Find it Yourself: There are runtime recursion and compile time recursions also depends on context. Most recursions are runtime only unless they generically written.
Iterative approach vs Recursive Approach
Both iterative solutions and recursive solutions wherever applicable can be used interchangeably until they exited without infinite executions.
Every Iterative problem can be converted and use it like linear recursion and all other recursions depends on our context.
Trade-offs
As recursion is never recommended to all the approaches where it could solved by even in iterative ways. Basically it takes much stacks to get computed and return the result. Most regular cases will leads in to the computational costs to times of powers of n or typically exponential times
Complexities are purely based up on algorithms we’re going to use in our base code of a method definition. More precisely depends on function calls that we made to and from a method we can say. Since they costs memory also, memory allocation wise also they are bad as we discussed about stacks above.
Wrapping up
So that’s the coverage about recursion.
You could read other blogs on Fork-Join pool and Completable futures in java.
[Yet to be written.]
