An iterative algorithm solves problems by repeating steps over and over, typically using a loop. Most of the algorithms you’ve written in your programming journey so far are likely iterative algorithms. Recursion is a method of problem-solving where you solve smaller instances of the problem until you arrive at a solution. Recursive algorithms rely on functions that call themselves. Any problem you can solve with an iterative algorithm, you can also solve with a recursive one; however, sometimes, a recursive algorithm is a more elegant solution.

You write a recursive algorithm inside of a function or method that calls itself. The code inside the function changes the input and passes in a new, different input the next time the function calls itself. Because of this, the function must have a base case: a condition that ends a recursive algorithm to stop it from continuing forever. Each time the function calls itself, it moves closer to the base case. Eventually, the base case condition is satisfied, the problem is solved, and the function stops calling itself. An algorithm that follows these rules satisfies the three laws of recursion:

■ A recursive algorithm must have a base case.

■ A recursive algorithm must change its state and move toward the base case.

■ A recursive algorithm must call itself recursively.

To help you understand how a recursive algorithm works, let’s take a look at finding the factorial of a number using both a recursive and iterative algorithm. The factorial of a number is the product of all positive integers less than or equal to the number. For example, the factorial of 5 is 5 × 4 × 3 × 2 × 1.

5! = 5 * 4 * 3 * 2 * 1 

Here is an iterative algorithm that calculates the factorial of a number, n:

def factorial(n):
 the_product = 1
 while n > 0:
   the_product *= n
   n = n - 1
 return the_product

Here is how to write the same algorithm recursively:
def factorial(n):
 if n == 0: 
   return 1
 return n * factorial(n - 1)

As you can now see, calculating the factorial of a number is a perfect example of a problem you can solve by finding solutions to smaller instances of the same problem. By recognizing that and writing a recursive algorithm, you created an elegant solution to calculate a number’s factorial.

When to Use Recursion How often you want to use recursion in your algorithms is up to you. Any algorithm you can write recursively, you can also write iteratively. The main advantage of recursion is how elegant it is. As you saw earlier, your iterative solution to calculate factorials took six lines of code, whereas your recursive solution took only four. A disadvantage of recursive algorithms is that they often take up more memory because they have to hold data on Python’s internal stack. Recursive functions can also be more difficult than iterative algorithms to read and debug because it can be harder to follow what is happening in a recursive algorithm.

Whether or not you use recursion to solve a problem depends on the specific situation, for example, how important memory usage is versus how much more elegant your recursive algorithm will be than a corresponding iterative algorithm. Later in the book, you will see more examples where recursion offers a more elegant solution than an iterative algorithm, like traversing a binary tree.