Python Recursion and Factorial

As the final Computer Science lesson of the 2016/2017 academic year, I reviewed the somewhat concept of recursion in the Python programming language. In this review, I used the mathematical concept of factorial to discuss recursion.

#Program Name: Recursion Sample
#Programmer Name: Eric Evans, M.Ed.
#Program Description: Provide a functional example of a recursion problem in Computer Science using the mathematical concept of factorial.
#
#Define function named factorial which will have an input value of n.
def factorial(n):
    print("Factorial has been called with n = " + str(n))
    if n == 1:
        return 1
    else:
        result = n * factorial(n-1)
        print(n,"! = ",result)
        return result
#Output the function factorial with an input value of 4.
print(factorial(4))

Let’s pull this concept apart line-by-line.

Lines 1 through 5 and line 14 are comment lines and have no real bearing on the program. They simply exist for documentation purposes.

At line 6, we declare a new function named “factorial” that will receive an input of “n”. This is done using the def or define call in Python. The “factorial” function occupies lines 6 through 13.

On line 7, we output the text “Factorial has been called with n = ” concatenated with the value of “n” cast as a string.

On lines 8 and 9, we enter the first part of a conditional statement. At line 8, we use a Boolean equals to see if “n” is equal to 1. If “n” is equal to 1, then line 8 executes and returns the value “1”.

Line 10 begins the process of addressing what to do if “n” does not equal 1.

On line 11, we declare a variable named “result”, which is defined as the value of “n” multiplied by the value of the “factorial” function with an input value that is one less than the current value of “n”.

Line 12 is simply allowing us to see the factorial value of the current “n” value each time through the loop.

Line 13 returns the value of the variable named “result”.

Line 15 calls the “factorial” function and provides it the necessary input to process. In this case, it is a 4.

Now, let’s see what happens when we run this code:

Factorial has been called with n = 4
Factorial has been called with n = 3
Factorial has been called with n = 2
Factorial has been called with n = 1
2 ! =  2
3 ! =  6
4 ! =  24
24

So, let’s see what’s going on with this output.

Lines 1 through 4 of the output are generated by line 7 of the code. That code displays the static words with the dynamic output of the value of “n”. Notice that each time through the loop, it decremented by 1.

Looking at lines 5 through 7 of the output, we see that the calculations actually start with the lowest factorial number of 2 and increment by 1.

Now, if you notice, the way the calculation was coded on line 11, we are performing the following:

  • (Step 1)  4! = 4 X 3!
    • This is the original problem. Solve for 4!, but it is defined needing to know the value of 3!, which is defined in step 2.
  • (Step 2)  3! = 3 X 2!
    • To solve step 1, we need to know the value of 3!. However, it is defined needing to know the value of 2!, which is defined in step 3.
  • (Step 3)  2! = 2 X 1!
    • To solve step 2, we need to know the value of 2!. However, it is defined needing to know the value of 1!, which is defined in step 4.
  • (Step 4)  1! = 1
    • To solve 3, we need to know the value of 1!. It has a given value of 1.
  • (Step 5)  2! = 2 X 1 = 2
    • Now, that we know the value of 1!, we can calculate the value of 2!.
  • (Step 6)  3! = 3 X 2 = 6
    • Now that we know the value of 2!, we can calculate the value of 3!.
  • (Step 7)  4! = 4 X 6 = 24
    • Now that we know the value of 3!, we can calculate the value of 4!, which was the original problem.

As you can see, the final solution is dependent upon the solution of a previous step, which was dependent upon the solution of a previous step, which was dependent upon the solution of a previous step, which – well you get the idea. This is the basic concept of recursion.

Basic Variables in Python

Today, we have been playing with basic variables in Python. The plan is to output something similar to the following:

Hello World
1 + 1 = 2
2 + 2 = 4
4 + 4 = 8

This output is to be generated entirely from calling variables.

#Programmer Name: Eric Evans, M.Ed.
#Program Name: 02 - Hello Variable
#Program Description: Outputs assigned information using only variables.
#
#DECLARATION OF VARIABLES
firstWord = "Hello"
secondWord = "World"
space = ' '
#OUTPUT
print(firstWord + space + secondWord)

Now, as you can see, the first line of the output is somewhat easy to code. We declared the variables firstWord, secondWord, and space and then called them to print concatenated together.

#Programmer Name: Eric Evans, M.Ed.
#Program Name: 02 - Hello Variable
#Program Description: Outputs assigned information using only variables.
#
#DECLARATION OF VARIABLES
firstWord = "Hello"
secondWord = "World"
space = ' '
firstAddend = 1
firstProblemSum = firstAddend + firstAddend
secondAddend = firstProblemSum
secondProblemSum = secondAddend + secondAddend
thirdAddend = secondProblemSum
thirdProblemSum = thirdAddend + thirdAddend
#OUTPUT
print(firstWord + space + secondWord)
print(firstAddend + " + " + firstAddend + " = " + firstProblemSum)
print(secondAddend + " + " + secondAddend + " = " + secondProblemSum)
print(thirdAddend + " + " + thirdAddend + " = " + thirdProblemSum)

Things start to act problematically when we try to produce the last 3 lines of output. When we run the application, we receive an error because we are attempting to mix string and integer variables on a combined output line.

To resolve this issue, we must typecast the integers as strings.

#Programmer Name: Eric Evans, M.Ed.
#Program Name: 02 - Hello Variable
#Program Description: Outputs assigned information using only variables.
#
#DECLARATION OF VARIABLES
firstWord = "Hello"
secondWord = "World"
space = ' '
firstAddend = 1
firstProblemSum = firstAddend + firstAddend
secondAddend = firstProblemSum
secondProblemSum = secondAddend + secondAddend
thirdAddend = secondProblemSum
thirdProblemSum = thirdAddend + thirdAddend
#CASTING OF VARIABLES
firstProblemSum = str(firstProblemSum)
firstAddend = str(firstAddend)
secondProblemSum = str(secondProblemSum)
secondAddend = str(secondAddend)
thirdProblemSum = str(thirdProblemSum)
thirdAddend = str(thirdAddend)
#OUTPUT
print(firstWord + space + secondWord)
print(firstAddend + " + " + firstAddend + " = " + firstProblemSum)
print(secondAddend + " + " + secondAddend + " = " + secondProblemSum)
print(thirdAddend + " + " + thirdAddend + " = " + thirdProblemSum)

As you can see, on lines 15 – 21 we cast each of the integer variables as a string variable. At this point, lines 24 – 26 will execute as expected.

The compilable code can be viewed at https://repl.it/HesM/3