1 of 2

Recursion Explained

Introduction to recursive functions

A recursive function is a function that calls itself until it doesn’t.

The following fn() function is a recursive function because it has a call to itself:

def fn():
    # ...
    fn()
    # ...
Code language: Python (python)

In the fn() function, the #... means other code.

Also, a recursive function needs to have a condition to stop calling itself. So you need to add an if statement like this:

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

Typically, you use a recursive function to divide a big problem that’s difficult to solve into smaller problems that are easier-to-solve.

In programming, you’ll often find the recursive functions used in data structures and algorithms like trees, graphs, and binary searches.

Python recursive function examples

Let’s take some examples of using the Python recursive functions.

1) A simple recursive function example in Python

Suppose you need to develop a countdown function that counts down from a specified number to zero.

For example, if you call the function that counts down from 3, it’ll show the following output:

3
2
1Code language: Python (python)

The following defines the count_down() function:

def count_down(start):
    """ Count down from a number  """
    print(start)Code language: Python (python)

If you call the count_down() function now:

count_down(3)Code language: Python (python)

…it’ll shows only the number 3.

To show the number 3, 2 and 1, you need to:

First, call the count_down(3) to show the number 3.
Second, call the count_down(2) to show the number 2.
Finally, call the count_down(1) to show the number 1.

In order to do so, inside the count_down() function, you’ll need to define a logic to call the function count_down() with argument 2, and 1.

To do it, you need to make the count_down() function recursive.

The following defines a recursive count_down() function and calls it by passing the number 3:

def count_down(start):
    """ Count down from a number  """
    print(start)
    count_down(start-1)


count_down(3)Code language: Python (python)

If you execute the program, you’ll see the following error:

RecursionError: maximum recursion depth exceeded while calling a Python objectCode language: Python (python)

The reason is that the count_down() calls itself indefinitely until the system stops it.

Since you need to stop counting down the number reaches zero. To do so, you add a condition like this:

def count_down(start):
    """ Count down from a number  """
    print(start)

    # call the count_down if the next
    # number is greater than 0
    next = start - 1
    if next > 0:
        count_down(next)


count_down(3)Code language: Python (python)

Output:

3
2
1Code language: Python (python)

In this example, the count_down() function only calls itself when the next number is greater than zero. In other words, if the next number is zero, it stops calling itself.

2) Using a recursive function to calculate the sum of a sequence

Suppose that you need to calculate a sum of a sequence e.g., from 1 to 100. A simple way to do this is to use a for loop with the range() function:

def sum(n):
    total = 0
    for index in range(n+1):
        total += index

    return total


result = sum(100)
print(result)Code language: Python (python)

Output:

5050Code language: Python (python)

To apply the recursion technique, you can calculate the sum of the sequence from 1 to n as follows:

sum(n) = n + sum(n-1)
sum(n-1) = n-1 + sum(n-2)
…
sum(0) = 0

The sum() function keeps calling itself as long as its argument is greater than zero.

The following defines the recursive version of the sum() function:

def sum(n):
    if n > 0:
        return n + sum(n-1)
    return 0


result = sum(100)
print(result)Code language: Python (python)

As you can see, the recursive function is much shorter and more readable.

If you use the ternary operator, the sum() will be even more concise:

def sum(n):
    return n + sum(n-1) if n > 0 else 0


result = sum(100)
print(result)
Code language: Python (python)

Summary

A recursive function is a function that calls itself until it doesn’t.
And a recursive function always has a condition that stops calling itself.

Recursion Examples

from typing import List, Optional, Sequence


# A recursive function is a function that calls itself. They're an alternative option to iteration, like using a while
# or for loop. Sometimes, they can make code easier to read and write. The examples below are overly simplified and
# have obviously better alternatives.

def multiply_string(s: str, n: int) -> str:
    # There are 3 main parts to a recursive function.
    # 1. A way to go to either the base case (no recursion) or recursive case (function calls itself).
    if n == 0:  # The switch between base and recursive is often an if statement.
        # 2. The base case. This is the case that doesn't require recursion.
        return ''  # Any string times 0 is empty string. That's easy.
    # 3. The recursive case. This same function gets called again, but slightly differently.
    # This needs to eventually get to the base case.
    return s + multiply_string(s, n - 1)  # Add the string to result of multiplying the string times n -1.
    # Eventually, n will be 0 and we'll be at the base case.


# This is also a good order to first write your recursive functions, even if you rewrite in a different order later.
# 1. What input is the base case?
# 2. What calculation needs to be done for the base case (if any)?
# 3. What calculation needs to be done for the recursive case?

# For the base case, there are some common patterns. It's often when an integer input is 0 or 1, the collection is
# totally empty, or you're at the thing you're looking for. A good question is: "What's the easiest possible case?"
# There can also be more than one base case! You've searched everywhere and haven't found the thing could be one
# base case, and you've found the thing could be another.
# For the recursive case, it's often easiest to think of being one step away from a base case. If your base case is
# n=0, think of how to get from n=0 to n=1. This is usually easier than how to get from n=9 to n=10.

def triangle_number(n: int) -> int:
    """Calculate the sum of 1, 2, n. This is like a triangle with n items on the bottom."""
    if n == 0:  # Easy case. n == 1 is just as easy, but this way our function also supports 0.
        return 0
    return n + triangle_number(n - 1)  # This will sum the numbers from highest to lowest. The calculation is like:
    # (3 + (2 + (1 + (0))))


# Recursive functions often have default arguments. These aren't used when you call the function from the outside,
# but they are used when you call the function recursively. They often hold data about the path to get where you are,
# or what you've already looked at.
def contains(item: object, sequence: Sequence, index: int = 0) -> bool:
    # When this function gets called by a user, they won't provide an index and we'll start at 0.
    if index == len(sequence):  # This means we've gone past the last index in the sequence.
        return False
    if sequence[index] == item:  # Another base case. We've found the item.
        return True
    # For the recursion, the item stays the same, the sequence stays the same, but let's check what's at the next index.
    # Any outside user of this function won't provide the index, but we can provide it now and check the next item.
    return contains(item, sequence, index + 1)


# The default arguments also might be mutated. This can help runtime. Rather than create a new thing every time,
# just mutate what was provided. Maybe you return it at the end.
def path_to_zero(n: int, path: Optional[List[int]] = None) -> List[int]:
    """Returns a list of how to get from n to 0 by subtracting 1."""
    if path is None:  # Classic Python mutable default stuff.
        path = []

    if n == 0:  # If we're already at 0 (the end)
        path.append(0)  # Our base case, no recursion required.
        return path
    else:
        path.append(n)  # Put the current number on the path.
        path_to_zero(n - 1, path)  # The path will get mutated in the recursive calls, adding the remaining numbers.
        return path


#  It can be helpful to write recursive functions in a verbose (if: base case, else: recursive) way, then refactor
#  them to be simpler. Here's the function above, refactored.
def path_to_zero_refactored(n: int, path: Optional[List[int]] = None) -> List[int]:
    if path is None:
        path = []

    path.append(n)  # Add the number we're at.
    if n:  # If we're not at 0
        path_to_zero_refactored(n - 1, path)  # Add the next thing until we are.
    return path


#  A good exercise is translating recursive functions to iterative, or vice versa.
def path_to_zero_iterative(n: int) -> List[int]:
    # This isn't the best code, but it's the closest to the recursive version above.
    path = []
    while n != 0:  # Recursive to iterative translations will often have "while not base case" loops.
        path.append(n)
        n -= 1  # This is the same transformation to n that happens in the recursive call above.
    path.append(0)  # Our while loop skips the base case, so we do it here.
    return path


#  The above examples are contrived, but this is an example where the recursive version makes for code that's just
#  as good or better than the iterative version.
def collatz(n: int, steps: int = 0) -> int:
    """Calculates how many steps to get from n to 1 following the Collatz rules.

    The Collatz rules are:
        If the number is even, get the next number by dividing it by 2.
        If the number is odd, get the next number by multiplying by 3 and adding 1.
    """
    if n == 1:  # We're at the end.
        return steps
    elif n % 2 == 0:  # If n is even
        return collatz(n // 2, steps + 1)
    else:  # n is odd
        return collatz(n * 3 + 1, steps + 1)  # Woah, a second recursive case!


# A downside to recursion in Python is that there is a limit to the call stack. This means there's a limit to how
# deep your recursion can go. The default is 1,000.
def deep_recursion():
    """Requires over 1,000 recursive calls, raising a RecursionError on most Python implementations."""
    collatz(9780657630)

# Those are some recursion in Python basics. Go find some other recursive problems and enjoy!

from typing import List, Optional, Sequence


# A recursive function is a function that calls itself. They're an alternative option to iteration, like using a while
# or for loop. Sometimes, they can make code easier to read and write. The examples below are overly simplified and
# have obviously better alternatives.

def multiply_string(s: str, n: int) -> str:
    # There are 3 main parts to a recursive function.
    # 1. A way to go to either the base case (no recursion) or recursive case (function calls itself).
    if n == 0:  # The switch between base and recursive is often an if statement.
        # 2. The base case. This is the case that doesn't require recursion.
        return ''  # Any string times 0 is empty string. That's easy.
    # 3. The recursive case. This same function gets called again, but slightly differently.
    # This needs to eventually get to the base case.
    return s + multiply_string(s, n - 1)  # Add the string to result of multiplying the string times n -1.
    # Eventually, n will be 0 and we'll be at the base case.


# This is also a good order to first write your recursive functions, even if you rewrite in a different order later.
# 1. What input is the base case?
# 2. What calculation needs to be done for the base case (if any)?
# 3. What calculation needs to be done for the recursive case?

# For the base case, there are some common patterns. It's often when an integer input is 0 or 1, the collection is
# totally empty, or you're at the thing you're looking for. A good question is: "What's the easiest possible case?"
# There can also be more than one base case! You've searched everywhere and haven't found the thing could be one
# base case, and you've found the thing could be another.
# For the recursive case, it's often easiest to think of being one step away from a base case. If your base case is
# n=0, think of how to get from n=0 to n=1. This is usually easier than how to get from n=9 to n=10.

def triangle_number(n: int) -> int:
    """Calculate the sum of 1, 2, n. This is like a triangle with n items on the bottom."""
    if n == 0:  # Easy case. n == 1 is just as easy, but this way our function also supports 0.
        return 0
    return n + triangle_number(n - 1)  # This will sum the numbers from highest to lowest. The calculation is like:
    # (3 + (2 + (1 + (0))))


# Recursive functions often have default arguments. These aren't used when you call the function from the outside,
# but they are used when you call the function recursively. They often hold data about the path to get where you are,
# or what you've already looked at.
def contains(item: object, sequence: Sequence, index: int = 0) -> bool:
    # When this function gets called by a user, they won't provide an index and we'll start at 0.
    if index == len(sequence):  # This means we've gone past the last index in the sequence.
        return False
    if sequence[index] == item:  # Another base case. We've found the item.
        return True
    # For the recursion, the item stays the same, the sequence stays the same, but let's check what's at the next index.
    # Any outside user of this function won't provide the index, but we can provide it now and check the next item.
    return contains(item, sequence, index + 1)


# The default arguments also might be mutated. This can help runtime. Rather than create a new thing every time,
# just mutate what was provided. Maybe you return it at the end.
def path_to_zero(n: int, path: Optional[List[int]] = None) -> List[int]:
    """Returns a list of how to get from n to 0 by subtracting 1."""
    if path is None:  # Classic Python mutable default stuff.
        path = []

    if n == 0:  # If we're already at 0 (the end)
        path.append(0)  # Our base case, no recursion required.
        return path
    else:
        path.append(n)  # Put the current number on the path.
        path_to_zero(n - 1, path)  # The path will get mutated in the recursive calls, adding the remaining numbers.
        return path


#  It can be helpful to write recursive functions in a verbose (if: base case, else: recursive) way, then refactor
#  them to be simpler. Here's the function above, refactored.
def path_to_zero_refactored(n: int, path: Optional[List[int]] = None) -> List[int]:
    if path is None:
        path = []

    path.append(n)  # Add the number we're at.
    if n:  # If we're not at 0
        path_to_zero_refactored(n - 1, path)  # Add the next thing until we are.
    return path


#  A good exercise is translating recursive functions to iterative, or vice versa.
def path_to_zero_iterative(n: int) -> List[int]:
    # This isn't the best code, but it's the closest to the recursive version above.
    path = []
    while n != 0:  # Recursive to iterative translations will often have "while not base case" loops.
        path.append(n)
        n -= 1  # This is the same transformation to n that happens in the recursive call above.
    path.append(0)  # Our while loop skips the base case, so we do it here.
    return path


#  The above examples are contrived, but this is an example where the recursive version makes for code that's just
#  as good or better than the iterative version.
def collatz(n: int, steps: int = 0) -> int:
    """Calculates how many steps to get from n to 1 following the Collatz rules.

    The Collatz rules are:
        If the number is even, get the next number by dividing it by 2.
        If the number is odd, get the next number by multiplying by 3 and adding 1.
    """
    if n == 1:  # We're at the end.
        return steps
    elif n % 2 == 0:  # If n is even
        return collatz(n // 2, steps + 1)
    else:  # n is odd
        return collatz(n * 3 + 1, steps + 1)  # Woah, a second recursive case!


# A downside to recursion in Python is that there is a limit to the call stack. This means there's a limit to how
# deep your recursion can go. The default is 1,000.
def deep_recursion():
    """Requires over 1,000 recursive calls, raising a RecursionError on most Python implementations."""
    collatz(9780657630)

# Those are some recursion in Python basics. Go find some other recursive problems and enjoy!

#recursions example-2
def factorial(n):
    print("Factoriaal called with " + str(n))
    if n < 2:
        print("Returning 1")
        return 1
    result = n * factorial(n - 1)
    print("Returning " + str(result) + " for factorial of " + str(n))
    return result
factorial(4)

#output
#Factoriaal called with 4
#Factoriaal called with 3
#Factoriaal called with 2
#Factoriaal called with 1
#Returning 1
#Returning 2 for factorial of 2
#Returning 6 for factorial of 3
#Returning 24 for factorial of 4

from collections.abc import MutableSequence

from src.typehints import T


def selection_sort_recur(seq: MutableSequence[T], i=0) -> None:
    """Use selection sort recursively on a list in-place."""
    if i >= len(seq) - 1:
        return
    min_val = min(seq[i:])
    min_val_i = seq.index(min_val, i)
    seq[min_val_i] = seq[i]
    seq[i] = min_val
    selection_sort_recur(seq, i + 1)

Recursion Examples

from typing import List, Optional, Sequence


# A recursive function is a function that calls itself. They're an alternative option to iteration, like using a while
# or for loop. Sometimes, they can make code easier to read and write. The examples below are overly simplified and
# have obviously better alternatives.

def multiply_string(s: str, n: int) -> str:
    # There are 3 main parts to a recursive function.
    # 1. A way to go to either the base case (no recursion) or recursive case (function calls itself).
    if n == 0:  # The switch between base and recursive is often an if statement.
        # 2. The base case. This is the case that doesn't require recursion.
        return ''  # Any string times 0 is empty string. That's easy.
    # 3. The recursive case. This same function gets called again, but slightly differently.
    # This needs to eventually get to the base case.
    return s + multiply_string(s, n - 1)  # Add the string to result of multiplying the string times n -1.
    # Eventually, n will be 0 and we'll be at the base case.


# This is also a good order to first write your recursive functions, even if you rewrite in a different order later.
# 1. What input is the base case?
# 2. What calculation needs to be done for the base case (if any)?
# 3. What calculation needs to be done for the recursive case?

# For the base case, there are some common patterns. It's often when an integer input is 0 or 1, the collection is
# totally empty, or you're at the thing you're looking for. A good question is: "What's the easiest possible case?"
# There can also be more than one base case! You've searched everywhere and haven't found the thing could be one
# base case, and you've found the thing could be another.
# For the recursive case, it's often easiest to think of being one step away from a base case. If your base case is
# n=0, think of how to get from n=0 to n=1. This is usually easier than how to get from n=9 to n=10.

def triangle_number(n: int) -> int:
    """Calculate the sum of 1, 2, n. This is like a triangle with n items on the bottom."""
    if n == 0:  # Easy case. n == 1 is just as easy, but this way our function also supports 0.
        return 0
    return n + triangle_number(n - 1)  # This will sum the numbers from highest to lowest. The calculation is like:
    # (3 + (2 + (1 + (0))))


# Recursive functions often have default arguments. These aren't used when you call the function from the outside,
# but they are used when you call the function recursively. They often hold data about the path to get where you are,
# or what you've already looked at.
def contains(item: object, sequence: Sequence, index: int = 0) -> bool:
    # When this function gets called by a user, they won't provide an index and we'll start at 0.
    if index == len(sequence):  # This means we've gone past the last index in the sequence.
        return False
    if sequence[index] == item:  # Another base case. We've found the item.
        return True
    # For the recursion, the item stays the same, the sequence stays the same, but let's check what's at the next index.
    # Any outside user of this function won't provide the index, but we can provide it now and check the next item.
    return contains(item, sequence, index + 1)


# The default arguments also might be mutated. This can help runtime. Rather than create a new thing every time,
# just mutate what was provided. Maybe you return it at the end.
def path_to_zero(n: int, path: Optional[List[int]] = None) -> List[int]:
    """Returns a list of how to get from n to 0 by subtracting 1."""
    if path is None:  # Classic Python mutable default stuff.
        path = []

    if n == 0:  # If we're already at 0 (the end)
        path.append(0)  # Our base case, no recursion required.
        return path
    else:
        path.append(n)  # Put the current number on the path.
        path_to_zero(n - 1, path)  # The path will get mutated in the recursive calls, adding the remaining numbers.
        return path


#  It can be helpful to write recursive functions in a verbose (if: base case, else: recursive) way, then refactor
#  them to be simpler. Here's the function above, refactored.
def path_to_zero_refactored(n: int, path: Optional[List[int]] = None) -> List[int]:
    if path is None:
        path = []

    path.append(n)  # Add the number we're at.
    if n:  # If we're not at 0
        path_to_zero_refactored(n - 1, path)  # Add the next thing until we are.
    return path


#  A good exercise is translating recursive functions to iterative, or vice versa.
def path_to_zero_iterative(n: int) -> List[int]:
    # This isn't the best code, but it's the closest to the recursive version above.
    path = []
    while n != 0:  # Recursive to iterative translations will often have "while not base case" loops.
        path.append(n)
        n -= 1  # This is the same transformation to n that happens in the recursive call above.
    path.append(0)  # Our while loop skips the base case, so we do it here.
    return path


#  The above examples are contrived, but this is an example where the recursive version makes for code that's just
#  as good or better than the iterative version.
def collatz(n: int, steps: int = 0) -> int:
    """Calculates how many steps to get from n to 1 following the Collatz rules.

    The Collatz rules are:
        If the number is even, get the next number by dividing it by 2.
        If the number is odd, get the next number by multiplying by 3 and adding 1.
    """
    if n == 1:  # We're at the end.
        return steps
    elif n % 2 == 0:  # If n is even
        return collatz(n // 2, steps + 1)
    else:  # n is odd
        return collatz(n * 3 + 1, steps + 1)  # Woah, a second recursive case!


# A downside to recursion in Python is that there is a limit to the call stack. This means there's a limit to how
# deep your recursion can go. The default is 1,000.
def deep_recursion():
    """Requires over 1,000 recursive calls, raising a RecursionError on most Python implementations."""
    collatz(9780657630)

# Those are some recursion in Python basics. Go find some other recursive problems and enjoy!

from typing import List, Optional, Sequence


# A recursive function is a function that calls itself. They're an alternative option to iteration, like using a while
# or for loop. Sometimes, they can make code easier to read and write. The examples below are overly simplified and
# have obviously better alternatives.

def multiply_string(s: str, n: int) -> str:
    # There are 3 main parts to a recursive function.
    # 1. A way to go to either the base case (no recursion) or recursive case (function calls itself).
    if n == 0:  # The switch between base and recursive is often an if statement.
        # 2. The base case. This is the case that doesn't require recursion.
        return ''  # Any string times 0 is empty string. That's easy.
    # 3. The recursive case. This same function gets called again, but slightly differently.
    # This needs to eventually get to the base case.
    return s + multiply_string(s, n - 1)  # Add the string to result of multiplying the string times n -1.
    # Eventually, n will be 0 and we'll be at the base case.


# This is also a good order to first write your recursive functions, even if you rewrite in a different order later.
# 1. What input is the base case?
# 2. What calculation needs to be done for the base case (if any)?
# 3. What calculation needs to be done for the recursive case?

# For the base case, there are some common patterns. It's often when an integer input is 0 or 1, the collection is
# totally empty, or you're at the thing you're looking for. A good question is: "What's the easiest possible case?"
# There can also be more than one base case! You've searched everywhere and haven't found the thing could be one
# base case, and you've found the thing could be another.
# For the recursive case, it's often easiest to think of being one step away from a base case. If your base case is
# n=0, think of how to get from n=0 to n=1. This is usually easier than how to get from n=9 to n=10.

def triangle_number(n: int) -> int:
    """Calculate the sum of 1, 2, n. This is like a triangle with n items on the bottom."""
    if n == 0:  # Easy case. n == 1 is just as easy, but this way our function also supports 0.
        return 0
    return n + triangle_number(n - 1)  # This will sum the numbers from highest to lowest. The calculation is like:
    # (3 + (2 + (1 + (0))))


# Recursive functions often have default arguments. These aren't used when you call the function from the outside,
# but they are used when you call the function recursively. They often hold data about the path to get where you are,
# or what you've already looked at.
def contains(item: object, sequence: Sequence, index: int = 0) -> bool:
    # When this function gets called by a user, they won't provide an index and we'll start at 0.
    if index == len(sequence):  # This means we've gone past the last index in the sequence.
        return False
    if sequence[index] == item:  # Another base case. We've found the item.
        return True
    # For the recursion, the item stays the same, the sequence stays the same, but let's check what's at the next index.
    # Any outside user of this function won't provide the index, but we can provide it now and check the next item.
    return contains(item, sequence, index + 1)


# The default arguments also might be mutated. This can help runtime. Rather than create a new thing every time,
# just mutate what was provided. Maybe you return it at the end.
def path_to_zero(n: int, path: Optional[List[int]] = None) -> List[int]:
    """Returns a list of how to get from n to 0 by subtracting 1."""
    if path is None:  # Classic Python mutable default stuff.
        path = []

    if n == 0:  # If we're already at 0 (the end)
        path.append(0)  # Our base case, no recursion required.
        return path
    else:
        path.append(n)  # Put the current number on the path.
        path_to_zero(n - 1, path)  # The path will get mutated in the recursive calls, adding the remaining numbers.
        return path


#  It can be helpful to write recursive functions in a verbose (if: base case, else: recursive) way, then refactor
#  them to be simpler. Here's the function above, refactored.
def path_to_zero_refactored(n: int, path: Optional[List[int]] = None) -> List[int]:
    if path is None:
        path = []

    path.append(n)  # Add the number we're at.
    if n:  # If we're not at 0
        path_to_zero_refactored(n - 1, path)  # Add the next thing until we are.
    return path


#  A good exercise is translating recursive functions to iterative, or vice versa.
def path_to_zero_iterative(n: int) -> List[int]:
    # This isn't the best code, but it's the closest to the recursive version above.
    path = []
    while n != 0:  # Recursive to iterative translations will often have "while not base case" loops.
        path.append(n)
        n -= 1  # This is the same transformation to n that happens in the recursive call above.
    path.append(0)  # Our while loop skips the base case, so we do it here.
    return path


#  The above examples are contrived, but this is an example where the recursive version makes for code that's just
#  as good or better than the iterative version.
def collatz(n: int, steps: int = 0) -> int:
    """Calculates how many steps to get from n to 1 following the Collatz rules.

    The Collatz rules are:
        If the number is even, get the next number by dividing it by 2.
        If the number is odd, get the next number by multiplying by 3 and adding 1.
    """
    if n == 1:  # We're at the end.
        return steps
    elif n % 2 == 0:  # If n is even
        return collatz(n // 2, steps + 1)
    else:  # n is odd
        return collatz(n * 3 + 1, steps + 1)  # Woah, a second recursive case!


# A downside to recursion in Python is that there is a limit to the call stack. This means there's a limit to how
# deep your recursion can go. The default is 1,000.
def deep_recursion():
    """Requires over 1,000 recursive calls, raising a RecursionError on most Python implementations."""
    collatz(9780657630)

# Those are some recursion in Python basics. Go find some other recursive problems and enjoy!

#recursions example-2
def factorial(n):
    print("Factoriaal called with " + str(n))
    if n < 2:
        print("Returning 1")
        return 1
    result = n * factorial(n - 1)
    print("Returning " + str(result) + " for factorial of " + str(n))
    return result
factorial(4)

#output
#Factoriaal called with 4
#Factoriaal called with 3
#Factoriaal called with 2
#Factoriaal called with 1
#Returning 1
#Returning 2 for factorial of 2
#Returning 6 for factorial of 3
#Returning 24 for factorial of 4

from collections.abc import MutableSequence

from src.typehints import T


def selection_sort_recur(seq: MutableSequence[T], i=0) -> None:
    """Use selection sort recursively on a list in-place."""
    if i >= len(seq) - 1:
        return
    min_val = min(seq[i:])
    min_val_i = seq.index(min_val, i)
    seq[min_val_i] = seq[i]
    seq[i] = min_val
    selection_sort_recur(seq, i + 1)

Recursion Explained

Introduction to recursive functions

A recursive function is a function that calls itself until it doesn’t.

The following fn() function is a recursive function because it has a call to itself:

def fn():
    # ...
    fn()
    # ...
Code language: Python (python)

In the fn() function, the #... means other code.

Also, a recursive function needs to have a condition to stop calling itself. So you need to add an if statement like this:

def fn():
    # ...
    if condition:
        # stop calling itself
    else:
        fn()
    # ...
Code language: Python (python)

Typically, you use a recursive function to divide a big problem that’s difficult to solve into smaller problems that are easier-to-solve.

In programming, you’ll often find the recursive functions used in data structures and algorithms like trees, graphs, and binary searches.

Python recursive function examples

Let’s take some examples of using the Python recursive functions.

1) A simple recursive function example in Python

Suppose you need to develop a countdown function that counts down from a specified number to zero.

For example, if you call the function that counts down from 3, it’ll show the following output:

3
2
1Code language: Python (python)

The following defines the count_down() function:

def count_down(start):
    """ Count down from a number  """
    print(start)Code language: Python (python)

If you call the count_down() function now:

count_down(3)Code language: Python (python)

…it’ll shows only the number 3.

To show the number 3, 2 and 1, you need to:

First, call the count_down(3) to show the number 3.
Second, call the count_down(2) to show the number 2.
Finally, call the count_down(1) to show the number 1.

In order to do so, inside the count_down() function, you’ll need to define a logic to call the function count_down() with argument 2, and 1.

To do it, you need to make the count_down() function recursive.

The following defines a recursive count_down() function and calls it by passing the number 3:

def count_down(start):
    """ Count down from a number  """
    print(start)
    count_down(start-1)


count_down(3)Code language: Python (python)

If you execute the program, you’ll see the following error:

RecursionError: maximum recursion depth exceeded while calling a Python objectCode language: Python (python)

The reason is that the count_down() calls itself indefinitely until the system stops it.

Since you need to stop counting down the number reaches zero. To do so, you add a condition like this:

def count_down(start):
    """ Count down from a number  """
    print(start)

    # call the count_down if the next
    # number is greater than 0
    next = start - 1
    if next > 0:
        count_down(next)


count_down(3)Code language: Python (python)

Output:

3
2
1Code language: Python (python)

In this example, the count_down() function only calls itself when the next number is greater than zero. In other words, if the next number is zero, it stops calling itself.

2) Using a recursive function to calculate the sum of a sequence

Suppose that you need to calculate a sum of a sequence e.g., from 1 to 100. A simple way to do this is to use a for loop with the range() function:

def sum(n):
    total = 0
    for index in range(n+1):
        total += index

    return total


result = sum(100)
print(result)Code language: Python (python)

Output:

5050Code language: Python (python)

To apply the recursion technique, you can calculate the sum of the sequence from 1 to n as follows:

sum(n) = n + sum(n-1)
sum(n-1) = n-1 + sum(n-2)
…
sum(0) = 0

The sum() function keeps calling itself as long as its argument is greater than zero.

The following defines the recursive version of the sum() function:

def sum(n):
    if n > 0:
        return n + sum(n-1)
    return 0


result = sum(100)
print(result)Code language: Python (python)

As you can see, the recursive function is much shorter and more readable.

If you use the ternary operator, the sum() will be even more concise:

def sum(n):
    return n + sum(n-1) if n > 0 else 0


result = sum(100)
print(result)
Code language: Python (python)

Summary

A recursive function is a function that calls itself until it doesn’t.
And a recursive function always has a condition that stops calling itself.