Suppose we want a function that take a parameter string
containing digits and should return the sum of all those digits.
For instance, “

”
should compute and return 14, from 3 + 1 + 4 + 1 + 5.
`add_digits`(`'31415'`)

You might easily imagine doing this using a

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.**for**

**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

— that ends up calling itself.
A function calling itself, such as this one, is called
a `add_digits`**recursive function**.

To see how this works, let's consider what happens when somebody
calls “

”.`add_digits`(`'314'`)

We enter

with the parameter`add_digits`

being “`numstr``314`

”. Since this string's length is more than one, we enter the

clause.**else**Inside the

, we first compute**else**

, which is the string “`numstr`[`1`:]`14`

”. Then we pass this string as a parameter to

.`add_digits`Now we enter

with the parameter`add_digits`

being “`numstr``14`

”. Since this string's length is more than one, we enter the

clause.**else**Inside the

, we first compute**else**

, which is the string “`numstr`[`1`:]`4`

”. Then we pass this string as a parameter to

.`add_digits`Now we enter

with the parameter`add_digits`

being “`numstr``4`

”. Since this string's length is one, the

clause.**if**Inside the

, we compute the integer to which the string corresponds, yielding the integer 4, which we return.**if**

Having received 4 from the recursive call, we store that in the

variable. The next line finds what integer the first digit in`sum_rest`

corresponds to — and at this level,`numstr`

is “`numstr``14`

”, so the first digit is the integer 1 — and adds to that the value in

, which is 4. The function returns this sum, 5.`sum_rest`

Having received 5 from the recursive call, we store that in the

variable. The next line finds what integer the first digit in`sum_rest`

corresponds to — and at this level,`numstr`

is “`numstr``314`

”, so the first digit is the integer 3 — and adds to that the value in

, which is 5. The function returns this sum, 8.`sum_rest`

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

, the base case is when the parameter string is just one character long.`add_digits`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

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.`add_digits`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,

should return the string `reverse`(`'straw'`)

.`'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

be the empty string, and it will
reverse the empty string. But in reversing the empty string, the
program will attempt to assign `rest`

to be the first
letter, and at that point the program will crash.`first`

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

or **for**

loops, but it's the
simplest place to start. We'll see later some more complex
applications of recursion.**while**