There are different programming languages like Python, Java, C, C++, Dart, Typescript, Javascript and all these Programming Languages have different ways of implementing recursion.
Recursion is a concept in programming that helps us resolve certain tasks or problems. It can be used to replace loops such as the for loop. In this article we are going to be talking about recursion and how we can implement it in different programming languages.
Introduction to recursion.
Let us consider a gift box bearing other gift boxes. If we open the first box we see another box in it. This continues until we reach the box that contains our gift. But if we want to close back all the boxes then we would have to start closing from the smallest box right up to the largest box which is the first box we opened.
In the image below we consider that the red box at the end is our gift and we need to open up 6 boxes for us to get our gift.
What is recursion.
From the above explanation we can say recursion refers to solving a big problem by breaking it down into smaller chunks until it reaches the last level. Then starts solving each chunk starting with the “base case” bit by bit until it reaches the largest chunk.
Using technical terms, we would say recursion is a concept in programming that allows us to define a function, and call that function in its function definition.
How it works.
When we define a recursive function, we need to define a condition that would help us break the calling of the function and start solving each chunk till we get the final answer. This condition is known as the base case or base condition.
Just like in our example of the gift box, we need to reach the red box before we can start closing it up all over again.
For example let write a function to add n numbers in an array
Algorithm
- First we need to look for the base case.
- Secondly we need to access each element in that array and add them together so that at the end we get the sum of all element in the array.
n <= 0 //this condition in the if statement refers to base condition.
Each time the code would run, it would check if it fulfils the condition if not it does the else statement until the base condition is fulfilled.
How the code runs
Let's consider the arguments passed in the function are ([1, 2, 3,4], 3)
First time:
Is n <= 0? No so it does the else statement
Which is addnums([1, 2, 3,4], 2) + arr[2]
Second time:
Is n <= 0? No so it does the else statement
Which is addnums([1, 2, 3,4], 1) + arr[1]
Third time:
Is n <= 0? No so it does the else statement
Which is addnums([1, 2, 3,4], 0) + arr[0]
Since n = 0 then it returns 0
Then it starts going upward
arr[0] = 1
arr[1] = 2
arr [2] = 3
So it takes 1+2+3 and gives 6
Some examples on recursion
Examples gotten from freeCodeCamp
1. Writing a function that uses recursion to create a countdown:
How to solve this problem
.
The code would define a function called countDown in javascript count_down in pyhton which takes one argument called n and if n is lesser than 1 then it returns an empty array
If not it cals defines a variable called count_array(or countArray) and give it a value of count_down(n - 1)( or countDown(n-1)) and for each value stored in count_array(countArray) it includes it in the array count_array(or countArray) and returns count_array as the final array.
Implementation in python
The output for this pythont code gives 5, 4, 3, 2, 1
Implementation in Javascript
The output for this Javascript code gives 5, 4, 3, 2, 1.
2. Use recursion to create a range of numbers:
How to solve this problem:
The code would define a function called range_of_numbers in python, rangeOfNumbers in javascript which takes two argument called startNum and endNum in javascript , start_num and end_num in python.
If startNum is equal to endNum then it should return the first argument which is addNum.
Else it assigns the value rangeOfNumbers(startNum, endNum -1) to the variable down and returns the variable down.
Implementation in python
The output for this python code gives [3, 4, 5, 6, 7] for the first case and [3] for the second case.
Implementation in Javascript
The output for this javascript code gives [3, 4, 5, 6, 7] for the first case and [3] for the second case.
Recursion can be used when we want to break down complex problems into smaller ones, replace the use of loops and also to make our code look cleaner.
But it should not be implemented in all cases since it is costly as it reserves a space in memory for each recursive call that is being made.
From the above article we have seen examples on how to use and implement recursion and I hope that you have understood what recursion is all about.
Thank you for reading.
you could connect with me on twitter
Top comments (0)