Skip to content
Home » Programming » Calculating Factorial Recursively in Python

Calculating Factorial Recursively in Python

Calculating-factorial-recursively-in-python

In this post, we will investigating the linguistic structure for calculating factorial recursively in Python.

Concept of Factorial

First let’s understand the concept of factorial of a number. Factorial of a number is the result of multiplying that number by each of the integer values up to that number. For example, the factorial of the number 5 (often written as 5!) is 1 * 2 * 3 * 4 * 5 which equals to 120.

The factorial is not defined for negative numbers and the factorial of Zero is 1; that is 0! = 1.

Concept of Recursion in Python

Most computer programs support the idea of recursion and Python is no exception. In Python, it is perfectly legal to have a function that calls itself (that is within the body of the function a call is made to the same function). When the function is executed it will therefore call itself.

In Python, we can write a recursive function such as:

def recursive_function():
     print ('calling recursive_function')
     recursive_function()

Here, the function recursive_function() is defined such that it prints out a message and then calls itself. Note that no special syntax is required for this as a function does not need to have been completely defined before it is used.

Of course in the recursive_function() this will result in infinite recursion as there is no termination condition. However, this will only become apparent at runtime when Python will eventually generate an error.

However, as already mentioned a recursive function should have a recursive part and a termination or base case part. The termination condition identifies when the base case will apply. We should therefore add a condition to identify the termination scenario and what the base case behavior is.

Calculating Factorial Recursively in Python

We can create a recursive solution to the Factorial problem by defining a function that takes an integer to generate the factorial number for. This function will return the value 1 if the number passed in is 1 which is the base case. Otherwise, it will multiple the value passed into it with the result of calling itself (the factorial() function) with n – 1 which is the recursive part.

The function is given below.

def factorial(n):
      if n == 1:   # Termination condition
            return 1    # Base case
      else:
            res = n * factorial (n-1)   # Recursive Call
            return res

print (factorial(5))

The key to understanding this function is that it has:

  1. A termination condition that is guaranteed to execute when the value of n is 1. This is the base case; we cannot reduce the problem down any further as the factorial of 1 is 1.
  2. The function recursively calls itself but with n – 1 as the argument; this means each time it calls itself the value of n is smaller. Thus the value returned from this call is the result of a smaller computation.

To clarify how this works we can add some print statements (and a depth indicator) to the function to indicate its behavior.

def factorial (n, depth = 1):
    if n == 1:
         print ('\t' * depth, 'Returning 1')
    else:
         print ('\t' * depth, 'Recursively calling factorial(', n-1,')')
         result = n * factorial(n-1, depth+1)
         print('\t' * depth, 'Returning:', result)
         return result

print('Calling factorial(5)')
print(factorial(5))

When we run this version of the program then the output is:

Calling factorial(5)
    Recursively calling factorial(4)
        Recursively calling factorial(3)
            Recursively calling factorial(2)
                Recursively calling factorial(1)
                    Returning: 1
                Returning: 2
            Returning: 6
        Returning: 24
    Returning: 120
120

Note that the depth parameter is used merely to provide some indentation to the print statements.

From the output we can see that each call to the factorial program results in a simpler calculation until the point where we are asking for the value of 1! which is 1. This is returned as the result of calling factorial(1). This result is multiplied with the value of n prior to that; which was 2. The causes factorial(2) to return the value 2 and so on.

Leave a Reply

Your email address will not be published. Required fields are marked *