Self-paced

Explore our extensive collection of courses designed to help you master various subjects and skills. Whether you're a beginner or an advanced learner, there's something here for everyone.

Bootcamp

Learn live

Join us for our free workshops, webinars, and other events to learn more about our programs and get started on your journey to becoming a developer.

Upcoming live events

Learning library

For all the self-taught geeks out there, here is our content library with most of the learning materials we have produced throughout the years.

It makes sense to start learning by reading and watching videos about fundamentals and how things work.

Search from all Lessons


LoginGet Started
← Back to Lessons
Weekly Coding Challenge

Every week, we pick a real-life project to build your portfolio and get ready for a job. All projects are built with ChatGPT as co-pilot!

Start the Challenge
Podcast: Code Sets You Free

A tech-culture podcast where you learn to fight the enemies that blocks your way to become a successful professional in tech.

Listen the podcast
Edit on Github

What is recursion in Python?

Exploring Recursion in Python πŸ”„πŸ
Examples of Recursive Algorithms in Python πŸ“πŸ’‘

Exploring Recursion in Python πŸ”„πŸ

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.

What is Recursion in Python? πŸ”„πŸ”

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 (The Key to Recursion) πŸ—οΈπŸ§©

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.

CharacteristicDescription
Base caseIt will allow us to end the recursive call cycle of the function at some point and not enter an infinite call stack.
Recursive caseIn 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).

Pros and Cons of Recursion πŸŒŸπŸ“‰

Pros

  1. Conceptual simplicity: Some problems are naturally recursive and can be solved more simply and elegantly using recursion.
  2. Problem division: Recursion allows a problem to be divided into smaller subproblems, making it easier to solve.
  3. Code reduction: In certain cases, the use of recursion can result in more concise and readable code compared to iterative solutions.
  4. Application in recursive data structures: Data structures such as trees and linked lists are often handled more naturally and efficiently with recursive approaches.

Cons

  1. Memory consumption: Recursive calls can lead to higher memory usage, since each call adds a new instance on the call stack.
  2. Difficult to follow: Sometimes, the execution flow in recursion can be difficult to follow, which can make it difficult to debug and understand the code.
  3. Execution time: Recursive calls can lead to longer execution time due to call overhead and the need to manage the call stack.

Examples of Recursive Algorithms in Python πŸ“πŸ’‘

The following are some examples of recursion algorithms in Python.

Factorial Calculation

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.

Fibonacci Series

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.

Addition of Natural Numbers

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.

Conclusion

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! πŸ˜‰