In the previous lessons, we learned how to use while or for loops to repeat a part of our code. This type of repetition is called iteration, derived from the Latin verb for walking, because it just walks through your code over and over and executes it each time – until the halting condition applies. Besides iteration, programs also use recursion to perform repetitions.
What is recursion?
A recursive function is a function that contains a reference to itself, i.e. it calls upon itself. If it does not contain a valid halting condition, it may run infinitely. As this is usually not the goal, almost all recursive functions modify a variable before calling themselves again so at some point, the halting condition enters into force and the repetition stops.
How does it work?
Let’s use a simple example to illustrate recursion. You want to write a series of integers from a starting number (a) to a final number (z). How could you solve this? Assume you have never heard of while or for loops.
What you can do is define a function and call it for instance count. The function distinguishes between two cases:
a) a is equal to [or bigger than] z: the functions prints z
[Including the option of a being bigger than z prevents that the program runs forever because by incrementing a bigger value (a) by 1, it will never become equal to the smaller value (z). This is actually not really related to recursion but to conditionals. Alternatively, you could do a separate case for a bigger than z or just change the order of the conditions and define b and use an all-encompassing “else” for a]
→ This is the halting condition.
b) a is smaller than z: the function prints a and calls upon itself, but the variable a is replaced by a+1
Try to put the code together using your knowledge from previous lessons and it might look like this:
When you run your program (remember that defining a function is not enough, you need to use it to see results), you should get the desired result, for instance for a = 3 and z = 10:
When to use recursion?
As I said in the beginning, recursion is just another way to perform repetitions. In some cases, recursion is just easier to read or to implement than iteration like while or for loops. Other programing languages do not even have iteration so they rely on recursion. For you, as someone who is learning Python, it is important to know that recursion exists and how to use it, but you are probably not going to use it frequently.
For more detailed information, I recommend looking at Think Python by Allen B. Downey.
#mastery15
Learning with K26 