View unanswered posts | View active topics It is currently Wed May 25, 2016 1:56 am

 Page 1 of 1 [ 12 posts ]
 Print view Previous topic | Next topic
Life without recursion
Author Message
Rookie

Joined: Wed Jun 25, 2008 6:07 pm
Posts: 46
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 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
Guru

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
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)

Wed Oct 08, 2008 3:35 am
Rookie

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

 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
Guru

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
Re: Life without recursion
 Code:#include 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)

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
Rookie

Joined: Wed Jun 25, 2008 6:07 pm
Posts: 46
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
Guru

Joined: Sat Mar 01, 2008 12:52 pm
Posts: 1030
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) .

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)

Wed Oct 08, 2008 10:53 am
Rookie

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

Sun Oct 19, 2008 6:32 am
Rookie

Joined: Sat Nov 27, 2010 1:44 am
Posts: 34
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.

Sat Nov 27, 2010 2:02 am

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3654
Location: Rotterdam, The Netherlands
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
Rookie

Joined: Sat Nov 27, 2010 1:44 am
Posts: 34
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.

Sat Nov 27, 2010 10:14 am

Joined: Wed Mar 05, 2008 8:14 am
Posts: 3654
Location: Rotterdam, The Netherlands
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
Rookie

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

Mon Nov 14, 2011 8:21 am
Display posts from previous:  Sort by
 Page 1 of 1 [ 12 posts ]

#### Who is online

Users browsing this forum: No registered users and 0 guests

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

Search for:
 Jump to:  Select a forum ------------------ ROBOTC Applications    ROBOTC for LEGO MINDSTORMS       Third-party sensors    ROBOTC for CORTEX & PIC    ROBOTC for VEX IQ    ROBOTC for Arduino    Robot Virtual Worlds    Multi-Robot Communications    Issues and Bugs Competitions & Partners    Mini Urban Challenge    CS2N Robot Virtual Worlds Competitions       VEX Skyrise Competition 2014-2015       VEX Toss Up 2013-2014       FTC Block Party! 2013-2014    Competitions using VEX - BEST, TSA, VEX, and RoboFest!    FTC Programming    RoboCup Junior and Other ROBOT Competitions Virtual Brick Robotics Discussions    General Discussions    Project Discussions Off-Topic ROBOTC Forum & ROBOTC.net Suggestions/Feedback    ROBOTC Forums Suggestions/Comments    ROBOTC.net Suggestions/Comments       NXT Programming: Tips for Beginning with ROBOTC       VEX Programming: Tips for Beginning with ROBOTC    2013 Robotics Summer Of Learning       VEX Toss Up Programming Challenge       FTC Ring It Up! Programming Challenge    International Forums       Spanish Forums          ROBOTC for MINDSTORMS          ROBOTC for VEX       French Forums          ROBOTC pour Mindstorms          ROBOTC pour IFI VEX       Japanese Forums （日本語のフォーラム）       German Forums    2015 Spring Carnival Event    PLTW (Project Lead The Way)    Robotics Merit Badge    2014 Robotics Academy Summer of Learning