[DRAFT] How To: Recursion

[z05DSL3A]

As Recursion seems to pop-up every now and then I have started to write an Article on it (I will hopefully have it ready in a few days, time permitting). If anyone wants to suggest any particular aspect of or information about recursion to include please PM me.

---------------------------
Definition
Recursion (noun)
See: Recursion

COMPUT: a programming technique where a routine performs its task by delegating part of it to another instance of itself.

Introduction
For new computer science students, the concept of recursive programming is often difficult. Recursive thinking is difficult because it almost seems like circular reasoning. It's also not an intuitive process; when we give instructions to other people, we rarely direct them recursively.

For those of you who are new to computer programming, here's a simple definition of recursion: Recursion occurs when a function calls itself directly or indirectly.

A classic example of recursion
The classic example of recursive programming involves computing factorials. In mathematics, the factorial of a nonnegative integer, n (denoted n!) is the product of all positive integers less than or equal to n. For example, 5! is the same as 5*4*3*2*1, and 3! is 3*2*1.

An interesting property of a factorial is that the factorial of a number is equal to the starting number multiplied by the factorial of the number immediately below it. For example, 5! is the same as 5 * 4! You could almost write the factorial function as:

int factorial(int n)
{
   return n * factorial(n - 1);
}

^{Listing 1. First cut factorial function}

However, there is a small problem with this; it will run forever because there is no place where it stops calling itself. It therefore needs a condition to tell it to stop. Since a factorial is for positive numbers only it makes sense to stop the recursion when the input is 1 and return 1 as the result. The modified code will look like this:

int factorial(int n)
{
   if(n == 1)
   {
      return 1;
   }
   else
   {
      return n * factorial(n - 1);
   }
}

^{Listing 2. better factorial function}

As you can see, as long as the initial value is above zero, this function will terminate. Note that more work will need to be done to guard again invalid initial values.

The point at with the recursion is stopped is called the base case. A base case is the bottom point of a recursive program where the operation is so trivial as to be able to return an answer directly. In the case of a factorial 1! = 1. All recursive programs must have at least one base case and must guarantee that they will hit one eventually; otherwise the program would run forever or until the program ran out of memory or stack space.


Basic steps of recursive programs
All recursive programs follows the same basic sequence of steps:
1: Initialize the algorithm. Recursive programs often need a seed value to start with.
2: Check to see whether the current value(s) being processed match the base case. If so, process and return the value.
3: Redefine the answer in terms of a smaller or simpler sub-problem or sub-problems.
4: Run the algorithm on the sub-problem.
5: Combine the results in the formulation of the answer.
6: Return the results.


Using an inductive definition Writing provably correct programs Comparison with Loops

Tail-recursive functions
One of the concerns that people have with regards to recursive functions is the growth of the stack space. Some of the classes of recursive functions will indeed grow the stack space linearly with the number of times they recurs. However there is a class of recursive functions where the stack size remains constant regardless of the depth of recursion, tail-recursive functions.

Tail recursion
If a function call is the last thing a function does, then this call is called a tail-call. A recursion that uses a tail call is called tail-recursion. It would be worth looking at some examples of function calls to see exactly what is meant by a tail-call:

int func1()
{
    int a = 3;
    func1(); // recursive, but not a tail call.  
             // processing is continued after the function returns. 
    a = a + 4;
    return a;
}

int func2()
{
    int q = 4;
    q = q + 5;
    return q + func1(); // func1() is not in tail position.
                        // There is still more work to be
                        // done after func1() returns 
                        // adding q to the result
                         
}

int func3()
{
    int b = 5;
     b = b + 2;
     return func1();  // This is a tail-call.  The return value
                      // of func1() is used as the return value
                      // for this function.
}

int func4()
{
    func3();        // not in tail position 
    func3();        // not in tail position 
    return func3(); // in tail position 
}

^{Listing. Tail-calls and non-tail-calls}
For a call to be a true tail-call, no other operation can be performed on the result of the function before passing it back. As there is nothing left to do in the function, the actual stack frame for the function is not needed either.


Conclusion

External links _{http://en.wikipedia.org/wiki/Recursion_%28computer_science%29}

[Zaita]

I'd like to comment :)

Your tail recursive function would be an infinite loop in func1();. Also, that is also the only function that has any recursion in it.

I think it'd also be good to have a list of things you should not do with recursion. e.g Read the contents of a file =\

Some more samples:

#include <iostream>
#include <string>

using namespace std;

int getDiff(int X, int Y) { // Tail Implementation
  X++; // Inc X
  if (X == Y)
    return 1;

  return (1+getDiff(X, Y));
}


void getDiff2(int X, int Y, int Diff = 0) {
  X++;
  Diff++;

  if (X != Y)
    getDiff2(X, Y, Diff);
  else
    cout << "Diff Was: " << Diff << endl;

  return;
}

int main(void) {

  cout << "Difference Between 1 & 7 Is: " << getDiff(1, 7) << endl;
  getDiff2(2, 8);
  return 0;
}

[guestgulkan]

Question.
Would any of you very experienced programmers here if asked to code a interative loop (like a matematical series) think of using recursion or would that be a 'mistake' that a rookie programmer would leap to.

I say mistake because it seems that all of these series could be written as a tight while or for loop without all the overhead of function calls.

[z05DSL3A]

Zaita,

Your tail recursive function would be an infinite loop in func1();. Also, that is also the only function that has any recursion in it.

I was ware that the recursive function has an infinate loop, but I was trying to keep the code uncomplicated because the examples given are to demonstrate a tail-calls not recurion.

I think it'd also be good to have a list of things you should not do with recursion.

The article is unfinished, I am planning to address the do's and don't (including don't use recursion for mathematical series).

Thank you for your comments:

I will rename the article [draft]... untill it is compleate ;0)

[bnbertha]

I would always write loops. I think it is important to understand recursion and how it works but I would never recommend using it. I have worked at several companies who regard it as virtually a disciplinary offence putting a recursive call into the code.

It's like everything else, it's down to the problem being solved, the coding conventions you are working to and personal preference.

[Faldrax]

bnbertha - no quicksort for you then:-)

[bnbertha]

Good point, but no, I wouldn't use the 'traditional' way of doing it.

It would be something like this

http://alienryderflex.com/quicksort/


EDIT: completely unrelated but what time zone does this server work to? My watch says 10.08!

[Duthomhas]

Tail recursion is a powerful feature. I know that the GCC will optimize for it in C++ (at least).

But is it required by the C++ standard?

Methinks it dangerous to assume that you can compute an infinite series in an iterative language just because you've defined the function tail-recursively. In other words, it might be worth noting that this is a compiler-specific feature and should not be taken for granted.

[Zaita]

@Grey Wolf: no worries :) I figured you may have been half asleep when you posted this :P

@bnbertha: I am with you on using loops.

@guestgulkan: I try to avoid recursion as much as possible. The only time I find I have a valid need for it is doing translation work. Iterating through byte streams of XML type structures to translate them into objects in code. (Protocol handlers etc). But, even then I will try to code my solution using loops instead. Easier to debug loops than recursions.

[z05DSL3A]

Zaita,
My intention was just to post an outline of the article first while I work on the rest offline. The outline was intended for people to make suggestions against...I got a bit carried away and started filling it in. :0)

I'm quite enjoying 'reading up' on this subject again, now that I can appreciate the different views more than when i was at university. I may have to try it for goto. ;0)

[Duthomhas]

BTW. Don't change the definition. That's great!

[weaknessforcats]

Recursion has its place. Like elegent Tree functions.

I would be clear in the article that any recursion can be replaced by a loop.

Further, be sure the reader understandsd that each recursive call introduces a new stack frame. That means:
1) recursion is slower than a loop since the stack frame has to be created, maintained, then destpyed
2) the stack frames could consume the stack memory allocation. In the case of Windows, you get 1MB as a default. And once I was on an HPUX machine that limited you to 4096 bytes.

[mahlerfive]

Good start, just a couple comments:

1) To be technical, you can have the factorial of 0, which is actually equal to 1, so this should be included in your base case.

2) You may want to specify that there may be multiple base cases, since there is not always just one.

3) I think you should avoid talking about the stack at all until the concept of recursion itself is fully explained. I would assume that almost anyone who does not understand recursion yet has no idea what the stack is and how they relate. You may want to have discussion about the stack and its relation to recursion at the end of the article.

4) As a TA for a 1st year comp sci course for 4 years, the thing I noticed most was that once students grasped how recursion was working on a basic level (i.e., they could read a recursive function and understand what it was doing), they still had major problems actually trying to solve a problem with recursion. Most students just couldn't figure out how to "start". You may want to expand on that by providing a section that explains a strategy and takes them through an example of employing it.

[exception]

Is there any point in avoiding recursion besides optimization (including optimization for stack size)? (And, of course, company policy... "To err is human, to forgive is Not Company Policy." -- P. Deutch (also known for his quote "To iterate is human, to recurse, divine.", since we are on that topic...))
Of course I'm counting out situations in which the recursion doesn't have any advantages in terms of readibility and maintainability over the iterative alternative.

BTW, perhaps the fact that any iterative algorithm has a recursive alternative and vice versa is noteworthy.

[Zaita]

It's harder to debug a recursive function.