Understanding Recursion

To illustrate recursion, we start with a very simple function for computing string length, which obviously, will operate on strings.  So, a quick recap of strings in C, which are arrays of characters followed by a null terminating character.

    char *ptrHello = "hello";

In memory, say at address 1000 we have the string "hello":

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 (it skips the first letter, so is the string "ello").

Further, let's note that the C standard library has a function strlen — which we will use at first, though 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:

int stringLength ( char *strPtr ) {
    return strlen ( strPtr );  
}  

(1)

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 in all cases.  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:

int stringLength ( char *strPtr ) {
    if ( *strPtr == '\0' )  
        return 0;  
    return strlen ( strPtr );  
}

(2)

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".)

int stringLength ( char *strPtr ) {
    if ( *strPtr == '\0' )  
        return 0;  
    return 1 + strlen ( strPtr + 1 );  
}

(3)

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 ptrHello+1, or "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 version (3) produces correct answers, and in fact, the same answers stringLength versions (1) and (2) and as strlen itself, we can use it internally instead of strlen:

int stringLength ( char *strPtr ) {
    if ( \*strPtr == '\0' )  
        return 0;  
    return 1 + stringLength ( strPtr + 1 );  
}

(4)

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:

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)))) 
                                => 5

(5)

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.

In summary, recursive algorithms have several elements:

1. one or more terminating conditions
2. decomposition of the problem into one or more smaller problems
3. one or more recursive calls used to solve those smaller problems
4. some operations that compose the smaller solutions into the larger solution

In our above recursive implementation of string length:

• 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 one recursive call, to solve the shorter string, 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.

That concludes our introduction to recursion.  The next section looks at rewriting this string length operation in expression form, and the one after that looks at a special kind of recursion involving a tail call, which affords particularly efficiency.

Here is another way of writing up this recursive implementation, the following equivalent implementation uses expression syntax instead of statement syntax:

int stringLength ( char *strPtr ) {
    return strPtr[0] == '\0' ? 0 : 1 + stringLength ( strPtr + 1 );  
} 

(6)

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 ));

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):

    return 1 + stringLength ( ... );

(4-return)

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:

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 );  
}

(7)

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, we use 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 version (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 programming language 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