Recursion - "99 Bottles of Beer"


#1

Recursion - “99 Bottles of Beer”

This is a finely-crafted example and also full of humor, but some people are finding it challenging to understand.

The difficulty, I think, stems mainly from not understanding the concept of recursion itself, and partly from the sheer number of printf statements (having a masking effect.)

Here is a gentle introduction to recursion, with concrete examples at the end.

Consider a simple example first, using the English phrase:
GNU is not Unix

Let’s define GNU (recursively) as:
GNU := GNU is not Unix
This definition of GNU is recursive because GNU appears again on the right hand side of the definition.

Using the rule that X := y means “replace the occurrence of X in y with y”, we can expand GNU like this:
GNU is not Unix
GNU is not Unix is not Unix
GNU is not Unix is not Unix is not Unix
GNU is not Unix is not Unix is not Unix is not Unix

We can go ad infinitum.

For practical reasons, let’s revise GNU slightly so that we can limit the length of the recursion:
GNU (N) := GNU (N-1) is not Unix
with the boundary condition that GNU (0) := gnu

So we can expand GNU (3) like this:
GNU (3) := GNU (2) is not Unix
GNU (2) = GNU (1) is not Unix
GNU (1) = GNU (0) is not Unix
GNU (0) = gnu
After stopping at GNU (0) and back substituting we get:
GNU (3) = gnu is not Unix is not Unix is not Unix

Similarly, we can define the factorial of an integer number N (N>=0) like this:
Factorial (N) := N * Factorial (N - 1) or (Factorial (N) := Factorial (N - 1) * N)
with Factorial (0) := 1

Now in code:

//  main.m

#import <Foundation/Foundation.h>

typedef unsigned long count_type;
typedef unsigned long value_type;

static NSString * GNU (count_type);
static value_type Fac (count_type);

int main (int argc, const char * argv[])
{
    @autoreleasepool {
        NSLog (@"...");
        NSLog (@"GNU (0) = %@", GNU (0));
        NSLog (@"GNU (1) = %@", GNU (1));
        NSLog (@"GNU (2) = %@", GNU (2));
        NSLog (@"GNU (3) = %@", GNU (3));
        NSLog (@"GNU (4) = %@", GNU (4));
        NSLog (@"GNU (5) = %@", GNU (5));
        
        NSLog (@"...");
        NSLog (@"Fac (2) = %lu", Fac (2));
        NSLog (@"Fac (3) = %lu", Fac (3));
        NSLog (@"Fac (5) = %lu", Fac (5));
        NSLog (@"Fac (7) = %lu", Fac (7));
        NSLog (@"Fac (10) = %lu", Fac (10));
        NSLog (@"Fac (11) = %lu", Fac (11));
    }
    fflush (NULL);
    return 0;
}

static NSString * GNU (count_type n)
{
    if (n == 0)
        return @"gnu";   // stop the recursion
    else
        return [NSString stringWithFormat:@"%@ is not Unix", GNU (n-1)]; // next level of recursion
}

static value_type Fac (count_type n)
{
    if (n == 0)
        return 1;
    else {
        return n * Fac (n-1);
    }
}

Code output:

2012-07-12 10:53:06.545 GNU[35173:503] ...
2012-07-12 10:53:06.547 GNU[35173:503] GNU (0) = gnu
2012-07-12 10:53:06.548 GNU[35173:503] GNU (1) = gnu is not Unix
2012-07-12 10:53:06.548 GNU[35173:503] GNU (2) = gnu is not Unix is not Unix
2012-07-12 10:53:06.549 GNU[35173:503] GNU (3) = gnu is not Unix is not Unix is not Unix
2012-07-12 10:53:06.549 GNU[35173:503] GNU (4) = gnu is not Unix is not Unix is not Unix is not Unix
2012-07-12 10:53:06.550 GNU[35173:503] GNU (5) = gnu is not Unix is not Unix is not Unix is not Unix is not Unix
2012-07-12 10:53:06.550 GNU[35173:503] ...
2012-07-12 10:53:06.550 GNU[35173:503] Fac (2) = 2
2012-07-12 10:53:06.551 GNU[35173:503] Fac (3) = 6
2012-07-12 10:53:06.551 GNU[35173:503] Fac (5) = 120
2012-07-12 10:53:06.552 GNU[35173:503] Fac (7) = 5040
2012-07-12 10:53:06.552 GNU[35173:503] Fac (10) = 3628800
2012-07-12 10:53:06.552 GNU[35173:503] Fac (11) = 39916800

After this, the drink-alcohol example should make more sense.


#2

I am having problems following the logic in the example. I understand recursion (I think), where I get tripped up is following the flow after it prints “There are simply no more…” To my understanding, it is now out of the “else” block so how does it go back into that block and pick up the last “printf()” function? And then where is it directed to incrementally add the bottles into recycling? I am new to programming so if you could break this down for me, it would be very much appreciated.