Recursion Elimination

These demonstrations require a java-enabled browser.
If you have a slow modem, it may take a short while for the applets to load.

The first example is based on a really simple numeric recursive function:

    void thefunction(int param)
     {
       cout << param << endl;
       if (param>0)
         thefunction(param/10);
       cout << param << endl;
     }

    void main(void)
     {
       int x;
       cin >> x;
       thefunction(x);
       cout << \"done\" << endl;
     }

You should probably work out for yourself what it does before proceeding.

First, you can run through the plain recursive version to see what it does.

Then, you can see and run through the special version with recursion eliminated, and get a better idea of how recursion elimination works. Notice that the two possible positions correspond to the two places in thefunction at which execution could either start or continue: the beginning, and immediately after the recursive call.

This second example is based on a slightly less simple numeric recursive function. This one, in fact:

    void thefunction(int param)
     {
       if (param<=0)
          return;
       thefunction(param/10);
       cout << param%10 << endl;
       thefunction(param/8);
     }
    
    void main(void)
     { 
       int x;
       cin >> x;
       thefunction(x);
       cout << "done" << endl;
     }

If you can't work out what it does, don't worry. It doesn't do anything useful. It is just a demonstration.

First, you can run through the plain recursive version to see what it does. Don't make the input much more than a three digit number or it will take a long time to finish. For this version I have shown stach frames containing the more traditional "return-to" field instead of the more intuitive "execute-here" field used in the first example.

Then, you can see and run through the special version with recursion eliminated, and get a better idea of how recursion elimination works. Notice that the three possible positions correspond to the three places in thefunction at which execution could either start or continue: the beginning, and immediately after each of the recursive calls. There is no code after the second recursive call, so position 3 doesn't do anything. It is there to make the non-recursive version more exactly match the recursive version above.