What is Recursion?
A function that calls itself again and again till a base condition is reached is called a recursive function. This method solves a problem by calling a copy of itself on a smaller unit of the problem being solved. Each call to itself is called a recursive step, however it is important that a recursive function terminates given a valid base case.
Why Use Recursion in Problem Solving?
Recursive code is generally shorter and easier to write than iterative code and most useful for tasks that can be broken down into similar subtasks examples includes
a. Sorting
b. Searching and,
c. Tree traversals etc
Format of a Recursive Function
A recursive function performs a task in part by calling itself to perform the subtasks. At some point, the function encounters a subtask that it can perform without calling itself. Thus a recursive function can be sub divided into two parts.
A. Base Case: the base case is the case where the function does not recur itself. A recursive function can have one or more base cases depending on the problem being solved.
B. Recursive Case: this is the case where the function calls itself to perform a subtask. A recursive function can also have more than one recursive cases depending on the problem being solved.
All recursive functions can be written using the format below.
// base case(s)
If(test for base case 1)
return some base case value
Else if(test for another base case)
return some other base case value
… …
// Recursive cases
Else
return some work and then a recursive call
How a Recursive function works
We will talk through this using an example in this case considering a factorial function (n!)
The factorial of a number (n) is the product of all positive integers between n and 1.
Hence it's defined thus as
0! = 1
1! = 1
2! = 2*1
3! = 3*2*1
4! = 4*3*2*1
If we study the pattern we can say
1! = 1 (1–1) where (1–1) =0!
2! = 2(2–1) where (2–1) =1!
3! = 3*(3–1) where (3–1) =2!
4! = 4*(4–1) where (4–1) =3!
Thus the formula
n! = n * (n- 1) if n > 0
For the factorial problem, our base case is 0!, since 0! Will always be 1 and our recursive case is represented with the function f(n-1)
If we transform this into a code we will have
The code will be executed in the manner explained below:
Recall that a recursive function calls a copy of itself for each subtasks, this copy is stored in a stack memory that uses the LIFO pattern. Lets say we want to find the factorial of the value 4, if you study the diagram below, you will get a clearer view of how a recursive function works.
Recursion and Memory
Each recursive call makes a new copy of that method (actually only the variables) in memory. Once a method ends (that is, it returns some data), the copy of that returning method is removed from memory, however, If we get infinite recursion, the program may run out of memory and result in fatal stack overflow error. this is why a valid base case is always needed when considering to use a recursive algorithm to solve a problem.
Recursion versus Iteration
While discussing recursion, the basic question that comes to mind is: which way is better? –iteration or recursion? The answer to this question depends on what you are trying to do. A recursive approach makes it simpler to solve a problem that may not have the most obvious of answers. But, recursion adds overhead for each recursive call (it needs space on the stack memory).
Recursion
- Recursion terminates when a base case is reached.
- Each recursive call requires extra space on the stack memory.
- If we get infinite recursion, the program may run out of memory and result in stack overflow.
- Solutions to some problems are easier to formulate recursively.
Iteration
- Terminates when a condition is proven to be false.
- Each iteration does not require extra space.
- An infinite loop could loop forever since there is no extra memory being created.
- Iterative solutions to a problem may not always be as obvious as a recursive olution.
Example of Algorithms that make use of Recursion
1. Fibonacci, Factorial findings
2. Merge sort, Quick sort
3. Binary search
4. Tree traversals and
5. Graph traversals etc
Dear reader, Kindly leave a comment or send me a mail, if you have any suggestions on the topic or possible improvements let's learn and grow together.
If this article has benefited you in a way, don't forget to leave as much clap as u wish too, also feel free to follow for more articles, let's encourage ourselves.
Dont forget to also check me out in my other social platforms
https://x.com/dositadix.com
https://www.linkedin.com/in/divine-ositadinma-69644539b
https://dositadi.medium.com
Top comments (0)