View unanswered posts | View active topics It is currently Sun Oct 26, 2014 4:36 am






Reply to topic  [ 12 posts ] 
Life without recursion 
Author Message
Rookie

Joined: Wed Jun 25, 2008 6:07 pm
Posts: 46
Post Life without recursion
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.


Tue Oct 07, 2008 9:48 pm
Profile
Guru
User avatar

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
Post Re: Life without recursion
hello,
I never doubted that recursions can be evaded (right word?).
The point is: using recursions you can write sort of very compact, logic, and sophisticated code, and the memory management is extremely effective (if you don't know how much recursive funcntion calls will be needed each time).
Just compare the code for Fibonacci numbers, or for the "Towers of Hanoi" using recursion - or not.
And because RobotC has no heap, you'll have to define sth like "maxTreeDepth" - that's a significant and strong limitation, there's nothing needed like this when using recursions!

_________________
regards,
HaWe aka Ford
#define S sqrt(t+2*i*i)<2
#define F(a,b) for(a=0;a<b;++a)
float x,y,r,i,s,j,t,n;task main(){F(y,64){F(x,99){r=i=t=0;s=x/33-2;j=y/32-1;F(n,50&S){t=r*r-i*i;i=2*r*i+j;r=t+s;}if(S){PutPixel(x,y);}}}while(1)}


Wed Oct 08, 2008 3:35 am
Profile
Rookie

Joined: Wed Jun 25, 2008 6:07 pm
Posts: 46
Post Re: Life without recursion
Ford,

Ford Prefect wrote:
... using recursions you can write sort of very compact, logic, and sophisticated code ...

I would argue that you can write code that is just as compact, logical, and sophisticated without recursion. It is, however, more complex.

Ford Prefect wrote:
Just compare the code for Fibonacci numbers, or for the "Towers of Hanoi" using recursion - or not.

Here is a non-recursive towers of hanoi that uses only two lines of code. It is definitely 'compact, logical and sophisticated.'

Code:
#include <iostream>
using namespace std;

// Adapted from source written by Prasad Krishna available at http://www.datastructures.info/the-towers-of-hanoi/
void hanoiNonRecursive(int n)
{
   for (int x = 1; x < (1 << n); x++)
      cout << "Move from pole " << (x&x-1)%3 << " to pole " << (((x|x-1)+1)%3) << endl;
}

As for the fibonacci numbers -- the example I gave is only one way of solving the problem. There are, of course, others. Mathematically, the fibonacci sequence can be expressed as a closed form function, meaning that the numbers themselves can be computed from a single formula, with no recursion involved.

Here is source for using the closed form solution. It uses no recursion and only a single local variable (for convenience).

Code:
#include <math.h>

int fibonacciClosedForm(int n)
{
   double gr = (1. + sqrt(5.)) / 2.;
   return (int)(((pow(gr, n) - pow(1 - gr, n))/sqrt(5.)) + .5);
}

Once again, it produces the same output as the recursive solution.

Now, to address your biggest complaint:
Ford Prefect wrote:
And because RobotC has no heap, you'll have to define [things] like "maxTreeDepth" - that's a significant and strong limitation, there's nothing needed like this when using recursions!

I understand your concern. The thing to realize, though, is that when you are using recursion, you have the same limitation. The only difference is, without recursion, you have to explicitly decide how deep you can go when you write the code. With recursion, the depth is limited by the size of your call stack. If you go too deep, you end up with a stack overflow, which can potentially crash the system if you don't explicitly limit the depth just like I did in the code above.

Writing programs for the NXT (or any of the other RobotC supported platforms) is not like writing code for a PC. Your resources are limited, and the code you write should be more specific to the task at hand. Sometimes you have to give up on making "general code that could be used to solve any related problem" and just decide what, specifically, you are trying to do. Once you know exactly what you're trying to solve, you can set reasonable bounds on the problem, define logical limits, and simplify the code down to a point where it can be dealt with in the given limitations.

Once again, I'm not trying to imply that you should always give up recursion. The samples shown here are 'compact, logical and sophisticated,' which is, in fact, a problem sometimes. "Sophisticated" code can be extremely complex and hard to read. Going for the shortest solution is not always the best. In many cases it makes more sense to solve things differently because it's easier to understand.

What I am trying to say, is that having a compiler that does not support recursion (or pointers, or function pointers, or dynamic memory allocation, or objects, or whatever) should almost never keep you from being able to do what you're trying to do. Be creative! Do the same thing you do when your construction pieces don't quite fit the need of what you're trying to build. Improvise. Think up interesting and new alternatives.

I always look forward to seeing the amazing things our talented community can do.


Wed Oct 08, 2008 9:17 am
Profile
Guru
User avatar

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
Post Re: Life without recursion
Code:
#include <iostream>
using namespace std;
void hanoiNonRecursive(int n)
{
   for (int x = 1; x < (1 << n); x++)
      cout << "Move from pole " << (x&x-1)%3 << " to pole " << (((x|x-1)+1)%3) << endl;
}

I doubt that this code will work with RobotC!

Quote:
What I am trying to say, is that having a compiler that does not support recursion (or pointers, or function pointers, or dynamic memory allocation, or objects, or whatever) should almost never keep you from being able to do what you're trying to do. Be creative!

well, I do my very best.

et ceterum censeo: I'll appreciate recursions and pointers to come ;-)

_________________
regards,
HaWe aka Ford
#define S sqrt(t+2*i*i)<2
#define F(a,b) for(a=0;a<b;++a)
float x,y,r,i,s,j,t,n;task main(){F(y,64){F(x,99){r=i=t=0;s=x/33-2;j=y/32-1;F(n,50&S){t=r*r-i*i;i=2*r*i+j;r=t+s;}if(S){PutPixel(x,y);}}}while(1)}


Last edited by Ford Prefect on Wed Oct 08, 2008 12:47 pm, edited 1 time in total.



Wed Oct 08, 2008 9:20 am
Profile
Rookie

Joined: Wed Jun 25, 2008 6:07 pm
Posts: 46
Post Re: Life without recursion
Ford Prefect wrote:
I doubt that this code will work with RobotC!

That code uses "cout," which is a C++ stream used for writing to a PC console. So, you're right that at least some modification is required before running it on the NXT. However, I've adapted it here for you to try. Once you switch to a native RobotC print statement, the rest of the code works just fine:

Code:
void hanoiNonRecursive(int n)
{
    eraseDisplay();
    for (int x = 1; x < (1 << n); x++)
    {
        nxtScrollText("Move from %d to %d", (x & (x - 1)) % 3, (((x | (x-1)) + 1) % 3));

        // Make sure the screen doesn't scroll so fast we can't see the output (for runs with lots of disks)
        wait1Msec(500);
    }
}

task main()
{
    int numDisks = 3;

    hanoiNonRecursive(numDisks);

    // Leave the results on the screen until they quit
    while(true);
}


Just as food for thought, Fortran was an extremely popular and well used language for a very long time. It had no recursion (until Fortan90). For well over 30 years people were writing non-recursive code with it anyway.

I know... "When I was your age, we had to walk ten miles to school every day uphill in the snow...." (Actually, I never had the pleasure. I'm still in my twenties.)

The point is, they did it; we can too.


Last edited by AvidProgrammer on Thu Oct 09, 2008 9:02 am, edited 1 time in total.



Wed Oct 08, 2008 9:34 am
Profile
Guru
User avatar

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
Post Re: Life without recursion
yes, I remember Fortran. It was the first programming language I've learnt
(on a IBM/360, twice as large as a living room, with 1/1000 of the calculating power of a ARM7, programmed by a shoe box full of punched cards just to print the result of "multiply 6 by 8" on another punched card (*)- and before this, getting a dozen shoe boxes full of punched cards filled with error messages) :wink: .

What are 30 years? And what are 30 years for computer technologies?
Where is Fortran now?
And what was the need of inventing C?

"Many people were increasingly of the opinion that they'd all made a big mistake in coming down from the trees in the first place.
And some said that even the trees had been a bad move, and that no one should ever have left the oceans."


(*) = 42 *rofl*

_________________
regards,
HaWe aka Ford
#define S sqrt(t+2*i*i)<2
#define F(a,b) for(a=0;a<b;++a)
float x,y,r,i,s,j,t,n;task main(){F(y,64){F(x,99){r=i=t=0;s=x/33-2;j=y/32-1;F(n,50&S){t=r*r-i*i;i=2*r*i+j;r=t+s;}if(S){PutPixel(x,y);}}}while(1)}


Wed Oct 08, 2008 10:53 am
Profile
Rookie

Joined: Wed Oct 08, 2008 4:14 am
Posts: 8
Post Re: Life without recursion
hi,
Quote:
Once again, the same code can be rewritten without recursion.

I guess that's nothing new for those who know about the advantages if they had recursions... :?


Sun Oct 19, 2008 6:32 am
Profile
Rookie

Joined: Sat Nov 27, 2010 1:44 am
Posts: 34
Post Re: Life without recursion
Ok, maybe I can live w/o a stack/recursion. But no stack AND concurrent tasks? That's just crazy deadly: one has to guarantee that no two tasks concurrently use any function. Even hard-to-remember functions like min and max etc. Very, very error prone.

Crazy, crazy deadly.


Sat Nov 27, 2010 2:02 am
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3227
Location: Rotterdam, The Netherlands
Post Re: Life without recursion
While I wouldn't go as far as calling it "crazy" or "deadly", it's certainly a pain in the backside sometimes. You could "protect" your calls to functions that are used by multiple tasks with hogCpu() and releaseCpu(). While not ideal, it's better than hoping for the best.

- Xander

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Sat Nov 27, 2010 2:35 am
Profile WWW
Rookie

Joined: Sat Nov 27, 2010 1:44 am
Posts: 34
Post Re: Life without recursion
No, I really meant what I said: especially in a beginner's programing environment, this feature combo is, well, yes, rediculous (e.g.: what do you mean I can't call max or round or sign from both of these tasks?). I find it absolutely shocking.

Even for experts, it's fraught with peril, requiring constant, constant vigilence not to mess up that you (a) either assign every single function to a particular task and only call it from there, or (b) have some sort of locking mechansim (hogCPU or something more reasonable) to control the concurrency.

Please, please, please, please: just give us a stack. Please, and all will be forgiven.


Sat Nov 27, 2010 10:14 am
Profile
Moderator
Moderator
User avatar

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3227
Location: Rotterdam, The Netherlands
Post Re: Life without recursion
You could argue that beginners wouldn't use tasks and anyone who does should know the dangers of doing so. I highly doubt the devs will implement a stack, it would mean a complete rewrite of the VM -and- compiler.

- Xander

_________________
| Professional Conduit of Reasonableness
| (Title bestowed upon on the 8th day of November, 2013)
| My Blog: I'd Rather Be Building Robots
| ROBOTC 3rd Party Driver Suite: [Project Page]


Sat Nov 27, 2010 11:04 am
Profile WWW
Rookie

Joined: Mon Nov 14, 2011 5:06 am
Posts: 1
Post Re: Life without recursion
thanks for help


Mon Nov 14, 2011 8:21 am
Profile
Display posts from previous:  Sort by  
Reply to topic   [ 12 posts ] 

Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  



Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by ST Software for PTF.