Suppose we want a function that take a parameter string
containing digits and should return the sum of all those digits.
For instance, “add_digits('31415')
”
should compute and return 14, from 3 + 1 + 4 + 1 + 5.
You might easily imagine doing this using a for
loop
to iterate through each character in the string.
But right now I want to reflect on the alternative technique
implemented in the following definition.
def add_digits(numstr):
if len(numstr) == 1:
return int(numstr)
else:
sum_rest = add_digits(numstr[1:])
return int(numstr[0]) + sum_rest
This implementation is a departure from what we've seen
before because here we have a function — named
add_digits
— that ends up calling itself.
A function calling itself, such as this one, is called
a recursive function.
To see how this works, let's consider what happens when somebody
calls “add_digits('314')
”.
We enter add_digits
with the parameter numstr
being
“314
”. Since this string's length is more
than one, we enter the else
clause.
Inside the else
, we first compute numstr[1:]
,
which is the string “14
”. Then we pass this
string as a parameter to add_digits
.
Now we enter add_digits
with the parameter numstr
being “14
”. Since this string's length is more
than one, we enter the else
clause.
Inside the else
, we first compute numstr[1:]
,
which is the string “4
”. Then we pass this
string as a parameter to add_digits
.
Now we enter add_digits
with the parameter numstr
being “4
”. Since this string's length is one,
the if
clause.
Inside the if
, we compute the integer to which
the string corresponds, yielding the integer 4, which we
return.
Having received 4 from the recursive call, we store that
in the sum_rest
variable. The next line finds what
integer the first digit in numstr
corresponds to —
and at this level, numstr
is “14
”,
so the first digit is the integer 1 — and adds to that the
value in sum_rest
, which is 4. The function returns this
sum, 5.
Having received 5 from the recursive call, we store that
in the sum_rest
variable. The next line finds what
integer the first digit in numstr
corresponds to —
and at this level, numstr
is “314
”,
so the first digit is the integer 3 — and adds to that the
value in sum_rest
, which is 5. The function returns this
sum, 8.
Here are three things to keep in mind as you write recursive functions yourself.
Each recursive function must have a base case — some situation where the function is not recursive. After all, if there is no function, the function will always call itself, and it will never get around to returning. (In fact, since each recursive call takes up a bit of memory, eventually the program will exhaust the memory available to it, and the computer will crash it.)
In the case of add_digits
, the base case is when the
parameter string is just one character long.
Whenever there is recursion, the argument passed will be
“smaller” than it was originally — that is,
it will be closer to a base case. For example,
the add_digits
function calls itself with a string that
is one digit shorter than the string it was given, so the
lower-level call works with something that is closer to the base
case of a one-character string.
In handling the recursive case of a recursive function, it's helpful to think in terms of the magical assumption: Assume your function somehow magically works correctly for any argument smaller than the argument you're interested in. How can you use that to solve the problem for your parameter?
(By the way, the term “magical assumption” is just a phrase that I made up. And of course, there's nothing that's actually magical about recursion.)
Now let's consider how you can build your own recursive
function. Let's build a recursive function that, given a string, returns a
string with the letters reversed. For example, reverse('straw')
should return the string 'warts'
.
We start by reminding ourselves of the magical assumption: If we have a n-character string to reverse, how can the magical ability to reverse anything shorter than that help us to reverse an n-character string?
Here's an idea: Let's suppose we take everything but the first letter — traw — and reverse that to get wart. Then we just have to add the first letter after it. We implement this idea as follows.
def reverse(word): # We're not done yet!
first = word[0]
rest = word[1:]
rest_reversed = reverse(rest)
return rest_reversed + first
Of course, you have to wonder: How is it going to work on traw? Well, it'll go through the same procedure: Reverse raw to arrive at war and add a t on that to get wart.
But how does it reverse raw? It reverses aw to arrive at wa and adds an r to get war. And how does it reverse aw? It reverses w to arrive at w and adds a a to get wa.
But now things get a bit sticky. In reversing w, our
program will let rest
be the empty string, and it will
reverse the empty string. But in reversing the empty string, the
program will attempt to assign first
to be the first
letter, and at that point the program will crash.
What we need is a base case: some situation where no recursive calls are made. Every recursive function needs a base case so that it eventually terminates. In this case, our base case will be when we're asked to reverse a one-letter word: In that case, the word is the reverse of itself, so we can simply return that without any further processing. Adding that case gives us a complete, working function.
def reverse(word):
if len(word) <= 1:
return word
else:
first = word[0]
rest = word[1:]
rest_reversed = reverse(rest)
return rest_reversed + first
(By the way, this isn't the only possible answer. A very different approach would be to observe that we can reverse straw by dividing the string down the middle into two halves,st and raw, reversing each of those using the magical assumption, and then appending war and ts.)
For now, we're focusing on recursive functions that work in a
particular way: We are dealing with a sequence such as a list or
string as a parameter, and we are working recursively toward a
base-case of a one-element sequence. The examples you get this
way aren't particularly compelling, since you can easily imagine
doing them with for
or while
loops, but it's the
simplest place to start. We'll see later some more complex
applications of recursion.