Python Programming

So let us try another exercise for you to really understand recursive functions.

You will write a function named factorial() to compute the factorial of a positive integer.

As a reminder, the factorial of a number $n! = n \times (n-1) \times (n-2) \times ... \times 3 \times 2 \times 1$.

For example, factorial(4) should return 24 ($4 \times 3 \times 2 \times 1$).

For simplicity, assume that the input argument will always be a positive integer.

Task 1: Iteration

As a warm up, try to quickly whip up an implementation of factorial() that uses loops. Hopefully this is second nature to you by now, to the point where you do not even need to think about how to do this!

Task 2: Recursion

Now, how would you implement a recursive version of this problem? Try to think carefully about the problem before implementing anything (haven’t nagged you in a while now about this, have I?) You may need a pen and paper for this! 📃✒️

You may use the following diagram as a visual aid (and hint)! Look for a recurring pattern that you can ‘abstract’ out!

Try to also think of this problem at a more abstract level, from a ‘top-down’ view, rather than trying to ‘trace’ the output in detail. Remember that for recursive functions, you need to define two cases: a base case and a recursive/inductive case. So you can perhaps define these mathematically first?

$factorial(n) = \Bigg\{ \begin{array}{ll} ???? & n = 1 \\ ???? & n \gt 1 \\ \end{array}$

Your function will then simply implement this definition!

Note that this exercise will also involve the return value of your recursive function (compared to our previous countdown timer example that returns None).

Sample usage

>>> factorial(5)
120
>>> factorial(1)
1
>>> factorial(3)
6