RECURSION DEFINITION
Recursion is a computing technique where by a function calls itself during execution and add data to a stack memory till it reaches the end of the recursive loop and returns back the required output. Recursive algorithms are suited for problem whose data structure can be scaled down to smaller versions and they provide and alternative to the conventional iterative methods of approaching problems.
A visual example of how recursive algorithms work is the Russian doll,
As depicted above, the Russian doll has a smaller version contained in it till you get to the smallest doll, so also does recursive algorithms, they help solve problems that can be fragmented into smaller pieces but in this case each stage is stored in a STACK memory and can be recalled through a recursive path.
RECURSION VS ITERATION
The major difference between a recursive and iterative algorithm falls under three major criteria for review:
SPACE USAGE: Recursive algorithms are not space efficient when compared to iterative algorithms, this is because No stack memory is required in the case of iterative algorithms.
TIME EFFICIENCY: When it come to being time efficient iterative algorithms are more time efficient compared to recursive ones. Recursive algorithms require time to pop and push elements to stack memory which is less time efficient.
CODE SIZE: Recursion reduces the size of the code while iteration prolongs it. Hence recursive algorithms are easy to code.
3 STEPS FOR WRITING RECURSION ALGORITHM
Using an example of writing a recursive algorithm to determine the factorial of a number.
i. BUILD A RECURSIVE CASE - THIS DESCRIBES THE FLOW (GOVERNING EQN AND LOGIC).
n*factorial(n-1)
ii. SPECIFY A BASE CASE - THIS IS A STOPPING CRITERION TO PREVENT AN INFINITE LOOP
if n in [0,1]:
iii. IDENTIFY THE UNINTENTIONAL CASE - THIS PLACES A CONSTRAINT TO THE ALGORITHM
assert n>=0 and int(n) == n, "The number must be a positive integer only"
The code block above returns the factorial of the parameter 12 which is passed into the function.
The function calls itself each time and adds the each result variable in the stack memory till the base case ia achieved.
Top comments (0)