int strlen(char *s) { if(*s == '\0') return 0; else return 1 + strlen(s + 1); }
strlen()
works on
s+1
,
then we will compute the right
value of the length for string
s
.
In other words, if
strlen(s+1)
works, then
strlen(s)
works.
As flip as it sounds to say that if
strlen()
works, then
strlen()
works, that's really the best way to think about it.
When designing a recursive algorithm or function, you need to
assume that the algorithm already works.
Then you take a problem, and create a smaller version of the same
problem.
Once that one is solved recursively (remember you assumed that you
already had a solution, so use it), you then ask yourself, how
can I take the solution to the simpler version of the problem and
construct the solution to the larger version.
This is exactly what we did when we developed the recursive
solution to the Towers of Hanoi.
We assumed that we already knew how to move the rings from one
tower to another.
So we can move n-1 rings from the source to the spare tower.
This uncover the nth ring on the source tower which we then
move to the destination tower.
Now we can use our magic solution for n-1 rings to move the n-1 from
the spare tower to the destination placing them back on top of the
nth ring.
The result of all this is that we have moved n rings from the source
to the destination tower.
In other words, if we can move some number of rings, then we can
move one more than that number.
Since we can move a single ring, we can move any number of rings
by a domino effect.
This is also the basis of the mathematical proof technique called
mathematical induction.
In fact, we often prove things about recursive algorithms and functions
using induction.
The upshot of all this is that you really need to develop an intuitive sense of what recursion is and does. Don't ask how does it solve the problem? Ask instead how does it take a solution to a smaller problem and then build a solution to a bigger problem from it? It's natural to get hung up on the issue of how it gets the solution to the smaller problem in the first place. But don't let yourself do that. Keep focused on the fact that that will arise naturally if two things are true:
Recursion is that which is recursive.