Keys to recursion:

- base case: the “one line” operation that does the calculation
- state maintenance: remember the calculation result
- stop condition: logic that stops the recursion

An example to illustrate:

```
# calculate the sum of all integers up to n
def tail_recursive_sum(n, total=0):
if n == 0: # the stop condition
return total
total += n # the base case
return sum(n-1, total) # total is used to maintain the state
# simplified version
def sum(n, total=0):
if n== 0: return total
return sum(n-1, total+n)
```

Another way to write this function:

```
def recursive_sum(n):
if n == 1:
return 1
return n + sum(n-1)
```

The main difference is that `recursive_sum`

does not use a variable to maintain the state. It relies on the function call stack. Assuming `cur = 3`

, the above function call looks like this:

```
3 + sum(3-1)
3 + 2 + sum(2-1)
3 + 2 + 1
```

Notice that the 1st and 2nd call cannot be completed unless the 3rd call returns 1.

The call stack looks quite different with the `tail_recursive_sum`

approach:

```
sum(3-1, 0+3)
sum(2-1, 3+2)
sum(1-1, 5+1)
```

When there is no additional operations other than the recursive function call at the end of a function, it is called `tail recursion`

. (Some language support tail recursion optimization but Python doesn’t)

Here are some exercise to play with: