What is Recursion?
Recursion is the process by which a function calls itself either directly or indirectly. Using a recursive algorithm, certain problems are solved easily. Examples include Towers of Hanoi, Fibonacci sequence and the factorial function. In a recursive algorithm, the computer is able to remember every previous value or result of the problem. This information is then held by the computer on the “activation stack” — which is the inside of each function's workspace. Every function has its own workspace.
All recursive algorithms include the following components:
Base Case - The base case is a way to return without making a recursive call
Work toward Base Case - This is where we make the problem simpler. For example, dividing list into two smaller parts
Recursive Call - It is where the same algorithm is used to solve a simpler version of the problem
Advantages of Recursive Programming
Recursion can reduce time complexity - An example of this is calculating Fibonacci sequence of numbers (where each number is the sum of the 2 preceding ones). If you calculate the fibonacci sequence up to a number “n” using recursion rather than iteration, the time to complete the task when compared to that of the iterative method will be much greater.
Recursion adds clarity and reduces the time needed to write and debug code - If the input into a function is going to be small, then recursion is certainly preferable to prevent the program from getting cluttered.
Recursion works great with tree traversal - The tree data structure is a collection of entities that are linked to one another. One of the more efficient ways to traverse these trees when looking for an entity, is by recursively following a single branch until the end of that branch till the required value is found.
Disadvantages of Recursive Programming
Recursion requires more memory - Since the function has to add to the stack every recursive call and store the values there until the call is finished, the memory allocation is greater compared to an iterative function.
Recursion can be slow - Recursion is slow because it requires the allocation of a new stack frame. It is also difficult and takes a long time to write.
Article was written for CyberClubNPSi
Коментари