Life without recursion

AvidProgrammer · Tue Oct 07, 2008 9:48 pm

I've been watching some of the comments lately regarding features that aren't (currently) present in RobotC. While it's true that some of the things that are missing are powerful tools, it's also true that there is a lot you can do without them.

Recursion, for example, is an extremely convenient way of doing certain kinds of tasks. Nonetheless, it is never required. Any program written using recursion can be written without it. Sometimes it just requires a little extra creativity and thinking about the problem in a different way. Is it more challenging to write certain programs without recursion? Certainly. But, isn't that the point? Nearly everything people typically build with robot kits could be bought off the shelf already completed -- but that would take away most of the fun.

Here, I will present several tasks that people might use with recursion, and show how the same task could be implemented without recursion.

First, factorial. Factorials are easy to explain recursively: n! = n * (n - 1)! As code, this becomes:


	Code: int factorialRecursive(int val) { int result; if (val == 1) result = 1; else result = val * factorialRecursive(val - 1); return result; }

Yet -- the same code can be accomplished with a simple loop:


	Code: int factorialNonRecursive(int val) { int result = 1; while (val > 0) { result *= val; val--; } return result; }

Both of the previous functions produce the same result.

Next, computing Fibonacci numbers. Recursively, F(n) = F(n - 1) + F(n - 2) with F(1) = F(2) = 1. As code:


	Code: int fibonacciRecursive(int index) { int result; if (index <= 2) result = 1; else result = fibonacciRecursive(index - 1) + fibonacciRecursive(index - 2); return result; }

Once again, the same code can be rewritten without recursion. The only thing you need to do is keep some local variables to track the last two numbers so you can add them to get the next in the line. In fact, the code without recursion is considerably faster and requires less memory. (Keep in mind that calling any function requires memory -- even if there aren't any local variables in the function being called.)


	Code: int fibonacciNonRecursive(int index) { int history[2] = {1, 1}; int nextSum; int result; if (index <= 2) { result = 1; } else { index -= 2; while( index > 0) { nextSum = history[0] + history[1]; history[0] = history[1]; history[1] = nextSum; index--; } result = nextSum; } return result; }

Once again, both the previous functions produce the same output.

Now for something a bit more challenging: tree traversal. (Please note that the following code is not meant to be run on the NXT. If you want to see it work, compile it to run as a console app on your favorite operating system.)


	Code: #include <iostream> using namespace std; const int MAX_TREE_DEPTH = 10; typedef enum { IN, OUT } Direction; void handleNode(int depth, int branch, Direction dir) { for (int i = 0; i < depth; i++) cout << " "; switch(dir) { case IN: cout << branch + 1 << " -->" << endl; break; case OUT: cout << "<-- " << branch + 1 << endl; break; } } void rDoNode(int branchCount, int treeDepth, int curDepth, int curBranch) { handleNode(curDepth, curBranch, IN); if (curDepth + 1 < treeDepth) for (int i = 0; i < branchCount; i++) rDoNode(branchCount, treeDepth, curDepth + 1, i); handleNode(curDepth, curBranch, OUT); } void treeRecursive(int branches, int depth) { for (int i = 0; i < branches; i++) rDoNode(branches, depth, 0, i); } void treeNonRecursive(int branchCount, int treeDepth) { int searchPos[MAX_TREE_DEPTH]; int curDepth = 0; memset(searchPos, 0, sizeof(searchPos)); do { // move down the branch to next leaf node while(curDepth < treeDepth) { handleNode(curDepth, searchPos[curDepth], IN); curDepth++; } // back out from this node/branch to the next branch do { curDepth--; handleNode(curDepth, searchPos[curDepth], OUT); searchPos[curDepth] = (searchPos[curDepth] + 1) % branchCount; } while (curDepth > 0 && searchPos[curDepth] == 0); } while (curDepth > 0 \|\| searchPos[0] != 0); }

If you run either the 'treeRecursive' or 'treeNonRecursive' functions, you will get the same result: an full tree will be displayed with opportunities for processing to occur at each node, including interior nodes as they are traversed.

How do things like this work? The same way recursion works. When you use recursion, you use the current thread's stack to save state information for you. The same work can be accomplished simply by saving the same data in your own local data area. (In the tree traversal example the 'searchPos' array is actually saving our place in the same way that the call stack would when using recursion.)

Once again -- is it more challenging to write code without recursion? Perhaps. Even so, it's possible to do everything you need to do. Just be creative and you'll be amazed by how much you can get done.

Whether or not a particular feature is present should never really stop you from getting your work done. There's always more than one way to get things done.

Life without recursion

Who is online