Recursion in programming is a very powerful tool, this is done with functions that call themselves over and over again. You can picture it as a kind of loop that iterates until a condition is met. Next we will see a brief example where we will use a recursive function to look for the maximum value in a list of numbers.
1def find_maximum_value(list): 2 if len(list) == 1: 3 # Base case or exit case 4 return list[0] 5 else: 6 # Recursive case 7 short_list = list[1:] 8 result = find_maximum_value(short_list) 9 if list[0] > result: 10 return list[0] 11 else: 12 return result 13 14list = [1, 4, 25, 5, 7, 8, 9, 2, 40, 3, 27] 15maximum_value = find_maximum_value(list) 16print(f"The maximum number of the list is: {maximum_value}")
code output:
1The maximum number of the list is: 40
In this example we make use of a recursive function to find the largest number in a list, in this code we first make use of a conditional structure if else to check if the length of the list is equal to 1, if so, we return the only number in the list. This would be the exit or base case, otherwise, we make a recursive call to the function find_maximum_value() and we transfer as parameter the list minus the first value, to trim the list in each recursive call and finally we return the maximum value between the first number of the original list and the result of the function.
The recursivity or recursion is a concept that comes from mathematics and that applies to the world of programming. It allows us to solve problems or tasks where they can be divided into sub-tasks whose functionality is the same. Since the subproblems to be solved are of the same nature, the same function can be used to solve them. In other words, a recursive function is one that is defined as a function of itself, so it repeatedly calls itself until it reaches an exit point.
You will better understand how recursion works with the help of the following video.
The base case is fundamental when working with recursion since it defines when the process of recursive calls should stop. If you do not define a suitable base case, the function could execute indefinitely, draining your computer's resources and causing a system error.
Placing an incorrect base case is a very common mistake for someone starting to work with recursion, so remember that when creating a recursive function, the first thing to do before creating the function logic, is to create the base case and make sure it is well defined to prevent the function from calling itself indefinitely.
| Characteristic | Description |
|---|---|
| Base case | It will allow us to end the recursive call cycle of the function at some point and not enter an infinite call stack. |
| Recursive case | In the recursive case we call the function over and over again in a stack of recursive calls, but we will get closer to the output solution (the base case). |
The following are some examples of recursion algorithms in Python.
Factorial calculus is a mathematical concept that involves multiplying a series of consecutive positive integers, starting from 1 up to a number n. It is recognized by the symbol "!", and is placed after the number. Example:
1// N Factorial 2n! = n * (n - 1) * (n - 2) * (n - 3) * ... 3 4 5// 5 Factorial 65! = 5 * 4 * 3 * 2 * 1 = 120
Example of factorial calculation using recursion with Python.
1def factorial(n): 2 if n < 0: 3 return "You cannot do a factorial calculation with a negative number." 4 5 if n == 0 or n == 1: 6 return 1 7 else: 8 return n * factorial(n - 1) 9 10print(factorial(5)) # output: 120 11print(factorial(3)) # output: 6 12print(factorial(15)) # output: 1307674368000 13print(factorial(-50)) # output: You cannot do a factorial calculation with a negative number.
In this example, we make use of recursion to find the factorial result of a number n. First as in any recursion function, we create the base case with the help of a conditional if else, if the number n is equal to 0 or is equal to 1 then we return the number 1 and break the recursion loop, otherwise, we call the function factorial() and pass the number (n - 1) to find the factorial of all numbers less than n recursively and return the result of the function multiplied by n.
The Fibonacci series is a numerical sequence in which each number is the sum of the two previous numbers, the sequence starts with 0 and 1, then each following number is the sum of the two previous numbers, example:
10, 1, 2, 3, 5, 8, 13, 21, 34 ...
Example of a fibonacci series using recursion.
1def fibonacci(n): 2 if n < 0: 3 return "The fibonacci series accepts only positive numbers" 4 5 fibonacci_list = [0, 1] 6 7 def recursion(number, list): 8 if list[-1] + list[-2] > n: 9 return list 10 else: 11 list.append(list[-1] + list[-2]) 12 return recursion(number, list) 13 14 return recursion(n, fibonacci_list) 15 16limit_number = 1000 17result = fibonacci(limit_number) 18print("Fibonacci serie: ", result)
code output:
1Fibonacci serie: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]
In this example we make use of recursion to find all the numbers of the fibonacci series less than 1000. In this case, the base case is if the sum of the last two numbers in the list is greater than our limit number n; if so, we return the array and finish the stack of recursive calls, otherwise we add the sum of the last two numbers to the list and make the recursive call with the modified list again and again until the base case condition is met.
The sum of natural numbers refers to the addition of all positive integers from 1 to a number n. In mathematical terms, it is represented as the sum of a finite sequence of natural numbers. Example:
1n = (n * n+1) / 2 2n = n + (n - 1) + (n - 2) + ... 3 47 = (7 * 8) / 2 = 28 57 = 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28
Example of addition of natural numbers using a recursive function.
1def sum_natural_numbers(n): 2 if n < 0: 3 return "The addition of natural numbers can only be done with positive numbers." 4 5 if n == 0: 6 return 0 7 else: 8 return n + sum_natural_numbers(n - 1) 9 10print(sum_natural_numbers(5)) # output: 15 11print(sum_natural_numbers(7)) # output: 28 12print(sum_natural_numbers(3)) # output: 6 13print(sum_natural_numbers(15)) # output: 120 14print(sum_natural_numbers(-20)) # output: The addition of natural numbers can only be done with positive numbers.
In this example, the base case is if the number entered by parameter is equal to 0, if so, then we return 0 and end the stack of recursive calls, otherwise, we call the function sum_natural_numbers() recursively and we pass as a parameter the number (n - 1), finally we return the result of the function plus the number n this will give us the sum of all the numbers from n to 1.
Recursion is a powerful tool in programming that allows us to solve problems by breaking them into smaller subproblems. By correctly understanding the base case and the recursive case, we can create efficient recursive algorithms. Recursion is a complex programming topic that requires practice to fully understand it, I recommend that you practice as much as you can doing examples like the ones seen in this article. You can check the 4Geeks Blog to learn more interesting content.
Have fun creating recursion algorithms for your own applications! 😉