This lesson concludes the three previous lessons on repetition methods. Now that we know how to use both while and for loops as well as recursion, we need to decide which method to use in which case. In the lesson about for, we have already discussed when to use which loop so this lesson is going to focus on when to choose recursion over iteration (loops). Nevertheless, we are still going to look at examples for both for and while loops, just to deepen our understanding.
Today’s example problem is generating factorials. A factorial n! is defined as the product of n and the factorial of the previous integer, (n-1)!, with the factorial of 0, 0!, being equal to 1.
Maybe you noticed that this definition is indeed recursive. So let’s try to write a program:
Alternatively, you can use a for or a while loop:
Comparison: Which program works best for factorial?
Obviously, the result of all three programs must be the same. Otherwise, we would know that we made a mistake. Let’s compare how each program performs in the categories “efficient” and “easy to use”.
- For efficiency, we just look at the amount of lines required, even though efficiency is much more than that. The reason is that for such a short and small problem the differences in execution are negligible. To define the factorial function, we needed 6 lines with recursion, 7 with the while loop and just 5 when using the for loop. Thus, the for loop wins here.
- “Easy to use” depends obviously on your personal preferences, but since the definition for factorials is recursive, it might be intuitive to do a program with recursion. However, if you prefer loops, these might be easier for you.
What I want you to see from this comparison, is that there is hardly ever going to be a clear winner, but rather it depends on the problem and your preferences.
But generally speaking, which repetition is better?
Still, the answer is, “It depends.” Depending on the case, one repetition may be easier to read and to understand than the other. Generally speaking, recursion tends to be shorter, but it may become slow and inefficient if the numbers used are very large – but there are ways to reduce this problem. If you want to see these pros and cons in direct contrast, you can look at Programiz.
Furthermore, there are cases when recursion can be quicker. For instance, if you want to sort a list, you can do a recursion that keeps dividing the lists into two lists of the same size and then merges these one-unit lists until you get a final sorted list. This is much quicker and thus more effective than an iterative solution that always looks for the minimum.
Fun fact: Actually, there is a fourth way to solve this problem and we have already learned it: You could just use the function math.factorial(n). If you don’t remember how to do this, you can go back to the lesson on importing functions. #mastery16
Learning with K26 