char *ptrHello = "hello";
In memory, say at address, 1000 we have the string:
1000 h
1001 e
1002 l
1003 l
1004 o
1005 '\0' -- the null character
ptrHello holds 1000
Let's also observe that ptrHello+1 would be 1001 and that is also a valid string — though shorter by 1.
Further, let's note that the C standard library has a function strlen, which we will use, and eventually replace. When we call the library's strlen, we won't worry about how it works, rather we simply trust that it does.
This is the point of view of the consuming client programmer: one of trusting that something (in a library or somewhere else) just works without knowing how it works.
As programmers, we alternate hats: sometimes we are an implementer crafting an algorithm or function, and other times we are consumers, just using some function(s).
As consumers we trust in the contract that some function will do what it says, if we provide it with the right arguments, and we don't worry much about specific implementation details. This is the nature of abstraction, hiding certain details so we can focus on more immediate concerns. This will be important to do in our look into recursion.
Here is our first version of stringLength — and this one not recursive:
(1)
int stringLength ( char *strPtr ) {
return strlen ( strPtr );
}
This implementation simply calls strlen. This is a valid implementation of a function to compute the length of a string. It does almost no work, simply invoking strlen. We should be able to convince ourselves with very high degree of confidence that stringLength produces the same answers as strlen.
Now, we will handle one case — the empty string — and then turn all the other cases over to strlen:
(2)
int stringLength ( char *strPtr ) {
if ( *strPtr == '\0' )
return 0;
return strlen ( strPtr );
}
This implementation (2) either returns 0 for the empty string, or else, it uses strlen to compute the length of a non-empty string. Here strlen is still doing almost all of the work. The only case we're handling directly is the case of the empty string.
Next, we're going to change our function to do a bit more work as follows: Recall that here an expression strPtr + 1 points to the second character of a string. (In our above string example, ptrHello + 1 would be 1001, which is the string "ello".)
(3)
int stringLength ( char *strPtr ) {
if ( *strPtr == '\0' )
return 0;
return 1 + strlen ( strPtr + 1 );
}
This implementation (3) also handles the empty string directly (as does (2)). It still calls strlen, however, it is now counting the first character of the string itself and only calling strlen to count the rest of the characters. Notice that, compared to (2), it advances the pointer that it passes to strlen by 1 character. So if we called stringLength ( ptrHello ), then strlen would be invoked with "ello", and after computing the length of "ello" and returning 4 to us, our stringLength adds 1 to that result, so returns 5, the correct answer for "hello".
We know it is ok to do the pointer arithmetic of strPtr+1 because we have first checked and handled the case of the empty string. So, if we reach the second return statement, we know the string is not empty, and thus must have at least one character.
Now for the fun part: as we have confidence that stringLength (3) produces correct answers, and in fact, the same answers stringLength (1) and (2) and as strlen itself, we can use it internally instead of strlen:
(4)
int stringLength ( char *strPtr ) {
if ( *strPtr == '\0' )
return 0;
return 1 + stringLength ( strPtr + 1 );
}
Our stringLength, version (4), is now recursive.
As much as possible I encourage looking at the recursive invocation of stringLength for what it does for us, the caller, rather than that it does recursion at all.
In particular, let's compare this version (4) with version (3). Version (3) works by relying upon strlen. Version (4) simply substitutes strlen for another function we know works the same: stringLength, and, by simply trusting that stringLength works we can expect it to continue to work for us internally. So, without diving into the recursion — we can see it will work properly.
So, one trick with recursion is to pretend that we are simply using the recursive routine rather than thinking through the complete recursion. In order to do this, we need to switch our hats from the implementer of stringLength to a user of stringLength. This is a bit tricky because normally we switch our hats between writing implementations (of functions) and using them at different places in our code. However, with recursion, we have to switch our hats within the implementation.
Now, we can also follow to observe the recursive approach. One way is to expand the source code in our minds, something like this:
(5)
stringLength ( "hello" )
1+stringLength ( "ello" )
1+(1+stringLength ( "llo" ))
1+(1+(1+stringLength ( "lo" )))
1+(1+(1+(1+stringLength ( "o" ))))
1+(1+(1+(1+(1+stringLength ( "" )))))
1+(1+(1+(1+(1+0))))
Each line represents the next recursive invocation, along with the addition of 1 for each character that is removed by each level of recursive invocation.
The following equivalent implementation uses expression syntax instead of statement syntax:
(6)
int stringLength ( char *strPtr ) {
return strPtr[0] == '\0' ? 0 : 1 + stringLength ( strPtr + 1 );
}
Using the expression syntax we can also inline one level of the recursion:
return strPtr[0] == '\0' ? 0 : 1 + (strPtr[1] == '\0' ? 0 : 1 + stringLength ( strPtr + 2 ));
and after a bit of optimization on some of the constants:
return strPtr[0] == '\0' ? 0 : (strPtr[1] == '\0' ? 1 : 2 + stringLength ( strPtr + 2 ));
To wrap up the discussion, recursive approaches have several elements:
- one or more terminating conditions
- decomposition of the problem into a smaller problem or problems
- a recursive call or calls used on those smaller problem or problems
- some operations that compose the smaller solution into the larger solution
- the terminating condition is the empty string, for which the answer is zero.
- the decomposition is working on a string that is 1 character shorter.
- we have the recursive call, and,
- after the recursive invocation solves the 1-shorter string problem for us, we simply add 1 to that result to compose the smaller solution into the larger solution.
Next, we look at enabling tail call. Tail call optimization is an optimization technique that allows a compiler or assembly writer to remove an invocation in certain cases, substituting it with a branch, which does not create an additional stack frame. When applicable to and applied to a recursive function, this can result in significant performance and space gains over the recursive approach.
Tail call optimization cannot be expressed in high level language, but it can be enabled or precluded by the specific code in the function.
Enabling tail calls requires that the recursive invocation returns directly to the caller without any additional computation on the result. This is not the case in (4):
(4r)
return 1 + stringLength ( ... );
Here we see that the return value from the recursive invocation is used in a simple computation, an addition of 1. This computation on the value returned by the recursive invocation precludes the tail call optimization.
However, we can transform our solution into one that does directly return the result of the recursive invocation; we do this by moving the addition of one before the recursive function that we're calling.
We're going to need a helper function, stringLengthPlus, and it will be the recursive one.
As with any recursion, we will attempt to understand this function first from the perspective of a consuming client programmer without looking inside the recursive implementation.
The contract for stringLengthPlus is that it receives an extra parameter: a length value. So, it takes two parameters: a string, and a length. It returns to the caller:
the length of the string + that initially supplied length value.
If we supply the initial length value with zero, then it will return just the length of the string. That's what stringLength does below:
(7)
int stringLength ( char *strPtr ) {
return stringLengthPlus ( strPtr, 0 );
}
int stringLengthPlus ( char *strPtr, int accumulatedLength ) {
if ( *strPtr == '\0' )
return accumulatedLength
return stringLengthPlus ( strPtr + 1, 1 + accumulatedLength );
}
In the case of the empty string, stringLengthPlus simply returns the parameter-supplied length for the answer, as in this case there are no characters in the string to add to that length. Hopefully, you can see that if stringLengthPlus is invoked on the empty string, and with a length value of zero it will return zero.
However, if stringLengthPlus is invoked on a non empty string, it will compute that strings length + any initially provided length value.
Internally, it uses that feature to request (of itself) to compute the length of a 1 shorter string. As it does this, it provides a meaningful length value that accounts for the characters already handled. For example, the following recursive calls are made in computing the length of "hello":
stringLengthPlus ( "hello", 0 )
stringLengthPlus ( "ello", 1 )
stringLengthPlus ( "llo", 2 )
stringLengthPlus ( "lo", 3 )
stringLengthPlus ( "o", 4 )
stringLengthPlus ( "", 5 ) => 5
As compared with (4), (7) effectively moves composition computation (the adding of one) from after the recursive invocation to before the recursive invocation. In other words, instead of computing (the add one operation) on the returned value as in (4), our computation (the add one operation) takes place during passing of parameters in (7).
Because there is no work being done after the recursive call, the underlying machine code implementation could eliminate the creation of each stack frame for the recursive call, potentially improving performance quite a bit.
When the underlying system uses the tail call optimization, the return statement from the inner most recursive call returns directly to the outer caller (in our case that would be stringLength)
The astute reader may notice that tail call optimization can be applied to non-recursive functions as well. For example, stringLength, version (7), is a candidate for tail call optimization: as it itself returns return value of stringLengthPlus unmodified. If tail call optimization were applied here as well then the inner most recursive call to stringLengthPlus would return directly to the caller of stringLength!
This post first appear on Erik Eidt's "Discussions on Programming Models" at http://erikeidt.blogspot.com/2018/02/understanding-recursion.html
