Introduction
With this simple blog post, I want to share with you what I have learned studying the concept of recursion.
What is recursion
Why we should study it
When we use it
What is recursion
Recursion is a programming technique where a function calls itself to perform a specific task or problem. This technique is particularly useful for solving problems that can be broken down into smaller sub-problems, where each sub-problem is similar to the original problem.
For example, you can think about a box that contains other boxes inside it, to explore the content of the big box you have to perform multiple times the action of opening the small "boxes"(recursive case), until you receive an empty box ( base case).
When a function calls itself, it creates a new instance of itself, called a recursive call. The new instance of the function executes independently of the original instance until it reaches a base case, which is a condition that stops the recursion from continuing.
For a deep understanding of recursion, I recommend you study also how a stack work.
Why we should study it
Recursion is a helpful way to solve difficult problems that can be broken into smaller problems. By studying recursion, you can solve these problems more easily. Recursion is commonly used in computer science for organizing data and creating efficient methods, so it's very important for someone who wants to make a career to understand this concept. In addition, when you apply for a programming job, you might be asked about recursion. So, learning recursion can help you prepare for these interviews and increase your chances of getting a programming job. To sum up, studying recursion is a valuable skill for anyone interested in computer science or programming. It can improve your problem-solving skills, optimize your code, and help you better understand complex data structures and methods.
When we use it
One example of recursion is in the calculation of factorials. The factorial of a number is the product of all the positive integers up to and including that number. For example, the factorial of 5 (written as 5!) is 5 x 4 x 3 x 2 x 1, which equals 120.
The factorial calculated with recursion is something like this:
Starting with n = 5
Getting near the base case
5! = 5*4! 5!=1
4! = 4*3! 4!=1
3! = 3*2! 3!=1
2! = 2*1! 2!=1
1! = 1 1==1 -->return 1
Getting back into the function stack
2! = 2*1
3! = 3*2
4! = 4*6
5! = 5*24 =120
For example, the factorial of 5 can be calculated using the following recursive function written in Python.
#factorial function in python
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(5)) # --> 120
This function checks if the input number is 1. If it is, the function returns 1, which is the base case. If the input number is not 1, the function calls itself with a smaller number (n-1), recursive case, as the argument and multiplies the result by the original number (n). This process continues until the base case is reached, and the final result is returned.
This example demonstrates how recursion can be used to solve a complex problem (calculating factorials) by breaking it down into smaller sub-problems (multiplying a number by the factorial of a smaller number), and how the use of recursion can simplify and streamline the solution.
Conclusion
I hope that with this simple introduction about recursion, you have a better understanding of recursion as a problem-solving technique.
Follow and support me:
Special thanks if you subscribe to my channel :)