Question about recursion

[helumpago]

... a kingdom of heaven if NXC had recursions...!

Quick question I've been wondering for quite awhile now; what are recursions? I seem to remember going over them in my C++ class a few years back, but we never went in-depth. Just a quick summary?

[mightor]

I split your question from the wish list to keep that on topic.

Anyway, recursion is when a function calls itself. A good example of this is the fibonacci function:

Code: Select all

fibonaci(int n)
{
    if(n==1) return 0;
    if(n==2) return 1;
    return fibonaci(n-1)+fibonaci(n-2);
}

It requires a stack in order to make this work and the Lego firmware does not have one that is capable of doing this. It would require a tremendous amount of rewriting to add it.

- Xander

[HaWe]

It requires a stack in order to make this work

do you really mean a "stack" or actually more a "heap" ?

[gloomyandy]

I'm pretty sure he means a stack, the normal implementation for a language that supports recursion is to use a stack to hold the local variables and the return address for a function, then each call gets a new stack frame allowing the use of recursion...

[HaWe]

really?
ok, but I had bet the memory for each recursive level would be allocated dynamically - I assumed that dynamic memory allocation is done on the heap.
IIRC stack is used for static variables, correct me if I'm wrong. But I really am no IT professional, and I'm gladly learning more about this issue.

[gloomyandy]

The reality of memory allocation in real world systems can get complex (and I've worked with lots and implemented a few)... But in general a stack is the usual data structure used for the storage of locals in languages that allow recursion.

Most of the common procedural languages (Java/C/Pascal/C++ etc.) will use a stack for locals and the return address. You could use the heap and create a new stack frame object for each call but why bother? A stack provides a very cheap way to allocate and deallocate the space and perfectly matches the allocation pattern (with the most recent frame allocated always being the first to be freed). More complex languages that allow closures may use the heap for stack frames but I don't think we are talking about those sorts of languages here.

There is no need to use the stack for statics since there is only a single copy of such variables, so they are typically allocated to a fixed location.

In systems (like Java), that allow the use of threads, each thread will have a separate stack and that stack will often be allocated from the heap (so in effect the stacks are located within the heap). Some systems will even use multiple stacks within a thread. So for instance leJOS allocates the stack objects from the heap and has two stacks per thread, the first contains local variables, while the second contains the return address and other call linkage information, doing things this way makes the implementation a little simpler and the VM run faster...

Hope the above makes some sort of sense...

[HaWe]

thanks, very interesting indeed.
if we looked at 2 different computer systems:
(1), a computer system which got a stack and uses recursion (maybe NXT with LeJos fw);
(2), the the memory architecture of the NXT with the (e) Lego fw.

Now what is the difference between the memory architecture of (1) opposite to (2)?

[gloomyandy]

You are really comparing two virtual machines here (the standard Lego firmware VM and the leJOS VM - designed to execute Java byte code). There are many, many differences.

One of them is that Java/leJOS was designed to allow recursion to be used and so has call/return instructions that use a stack for the return address and has instructions that expect local variables to be stored on the stack and references them using a stack frame register that points to the current frame.

The Lego VM is not designed to support recursion and so stores the return address in a fixed location associated with the clump/function/method being called. Similarly local variables are not stored in a stack like structure (and crucially are not referenced relative to a frame pointer), but are instead stored in a set of fixed locations which are statically allocated at compile time.

It is this major difference that makes adding recursion to NXC (which generates code to run on the Lego VM), so difficult.

Note I'm no expert on the Lego VM, but I'm reasonably sure the above is correct. If you want to learn more of the details take a look at the Lego Executable File Format document available from the advanced section of the Lego Mindstorms site.

[afanofosc]

I agree with gloomyandy. In the LEGO firmware all variables are global and every subroutine call stores the return address in a global variable at the point of the call and uses that same global variable in the return call within the called routine. That design doesn't support recursion.

John Hansen

[helumpago]

Anyway, recursion is when a function calls itself. A good example of this is the fibonacci function:

Code: Select all

fibonaci(int n)
{
    if(n==1) return 0;
    if(n==2) return 1;
    return fibonaci(n-1)+fibonaci(n-2);
}

It requires a stack in order to make this work and the Lego firmware does not have one that is capable of doing this. It would require a tremendous amount of rewriting to add it.

- Xander

Okay, thanks. that's all I wanted to know.