🔒 Locked

idea for recursive functions

Started by silverphyre673 Apr 9, 2005 at 4:17 AM 9 replies 1.1k views

Original Post

Apr 9, 2005 at 4:17 AM

well, recursive functions can be quite expensive when they call themselves many times:


int recur(unsigned a)
{
    if (a<1000000)
    {
        a+=1;
        recur(a);
    }
    return a;
}

this would call itself a million times if we sent it '0' as the initial argument, which is what we want. However, it then has to RETURN one million times, which is a big performance hit, although this is a quite useless function. So I have an idea: could you build an interpreted language on a low level that would specify if a function is recursive like recursive int recur (unsigned a) which would then be automatically sent the line number that called the program and would send it to each call on top, so when a recursive function hits a 'return' statement, instead of returning to the calling function, it returned to the line that called the first recursive function directly, transforming this:


0 int recur (unsigned a){
1    if (a<3){
2        ++a;
3        recur(a);}
4    return a;}
5
6 int main(){
7    return recur(0);}

which would look like this: main()<----- return 3 ->recur(0)|<- return 3 ->recur(1)|<- return 3 ->recur(2)|<- return 3 ->recur(3)| to this ( recursive is a madeup keyword):

 0 recursive int recur (int a, int line_number){ 1 if (a<3){ 2 ++a; 3 recur(a, line_number);} 4 return a; //returns to line 'line_number' in calling function 5 6 int main(){ 7 recur(0, 7); 8 return 0;}  which would look, as I see it, like this: main()<---------------- returns 3 directly to here (line 7) ->recur(0, 7) | ->recur(1, 7) | ->recur(2, 7) | ->recur(3, 7)| couldn't this save a lot of time? Who thinks I should implement it, as proof-of-concept? Thanks, whew, long post!

Illco

Apr 9, 2005 at 4:24 AM

I think you can't. We are all working on stack-based machines. The idea of a stack is that you push stuff on top (like the record of a function call) and pop stuff off the top (like those records). It is not meant to do stuff that is not on top.

Then, it is also not necessary. Most, if not all, recursive functions can be unrolled to be implemented as while loops. Recursion may be powerful, but it should be used with care and intelligence.

Returning the whole way at once, thus, defeats the basic idea of the current computer and also is not necessary.

Greetz,

Illco

auLucifer

Apr 9, 2005 at 4:25 AM

What about if on the return trip you are adding another 1?
You won't want to just dump the whole stack there

Morbo

Apr 9, 2005 at 4:34 AM

This is handled by some languages by using tail recursion. Basically, if the last line of a function is a recursive call, the call can be reduced to relacing the parameters on the stack and jumping back to the beginning of the stack. As long as the call is the last operation in the function, nothing is lost by the optimization. It's called 'tail recursion' since the recursive call has to be at the end (tail) of the function. Some languages ease this restriction a bit, but the concept is always the same.

In your example, you'd have to rewrite the function like so:

int recur(unsigned a){   if (a >= 1000000)      return a   return recur(a+1)}

Now, instead of the last line returning, it can simply replace the value of a with the new one, and jump back to the top. No call required.

iMalc

Apr 9, 2005 at 4:34 AM

Modern compilers are good at optimising such functions into their iterative form. It's called tail-recursion elimination. Inlining of a fixed number of recursion iterations also applies here. There is still some room for improvement for compilers here, but it's a case of diminishing returns (that was a pun).

All singly-recursive functions can be written as iterative functions, transforming the recursive call into a loop. Most of the time this is very easy to do, although it depends upon how much experience you've had doing this.

Multiply-recursive functions cannot usually be simplified down to remove all recursion. One recursive call can be eliminated, but there is usually no way to remove more than one recursive call. In this case, no compiler of different programming language, could do it either.

snk_kid

Apr 9, 2005 at 4:42 AM

Quote:
Original post by silverphyre673
So I have an idea: could you build an interpreted language on a low level that would specify if a function is recursive like

recursive int recur (unsigned a)

which would then be automatically sent the line number that called the program and would send it to each call on top, so when a recursive function hits a 'return' statement, instead of returning to the calling function, it returned to the line that called the first recursive function directly, transforming this:

Google up parital evaluation as an alternative, for example:

#include <cstddef>// parital evaluationtemplate< std::size_t N >  inline double pow(double x) {    return  pow<N % 2>(x) * pow<N / 2>(x * x);}template<>inline double pow<1u>(double x)  { return x; }template<>inline double pow<0u>(double x) {  return 1.0;  }// full evaluationtemplate < int x, int y >struct Pow { static const int result = x * Pow<x, y - 1>::result; };// template partial specializationtemplate < int x >struct Pow<x, 0> { static const int result = 1; };int main() {        const int foo = Pow<2,2>::result;  // evaluated all at compile-time    double bar = pow<2>(2.0);   // partially evaluated at compile-time}

[Edited by - snk_kid on April 9, 2005 5:42:59 AM]

ToohrVyk

Apr 9, 2005 at 4:43 AM

What you are describing is called tail recursion. It is one of the basic foundations of functional languages, where recursion can almost always be performed in constant stack space.

There are several ways to implement tail recursion:
- Using closures, you basically "save" the call instead of performing. Then, you pop all your data off the stack and call the saved closure by using your own return address as a return address.
- Using continuations, you save the recursive call, give your own continuation to it, and use it as your continuation.
- At an even lower level, you modify the arguments in-place on the stack, and jump back to the top of your body.

Tail recursion is extremely easy to detect: a simple connexity algorithm determines where the recursive calls occur, and if you directly return the result of a recursive call, you can do it tail-recursively.

I have implemented tail recursion in a compiler project two months ago. I can tell you more about it if you wish.

Quote:
I think you can't. We are all working on stack-based machines. The idea of a stack is that you push stuff on top (like the record of a function call) and pop stuff off the top (like those records). It is not meant to do stuff that is not on top.

Yes it is, you can have pointers to objects on the stack (basically what happens when you allocate a char array on the stack in C) and can "unroll" the stack a fixed distance instead of object by object.

Quote:
Then, it is also not necessary. Most, if not all, recursive functions can be unrolled to be implemented as while loops. Recursion may be powerful, but it should be used with care and intelligence.

Tail-recursion is, if you look closer at its implementation, automatic loop unrolling. And some recursive functions (such as the MacCarthy 91 function) cannot be unrolled to a loop without the use of an additional stack.

Quote:
Returning the whole way at once, thus, defeats the basic idea of the current computer and also is not necessary.

And how, exactly, does it defeat the basic idea of the current computer?

ToohrVyk

Apr 9, 2005 at 4:56 AM

Quote:
Original post by iMalc
All singly-recursive functions can be written as iterative functions, transforming the recursive call into a loop. Most of the time this is very easy to do, although it depends upon how much experience you've had doing this.

Some recursive functions are inherently not tail-recursive, even when they are singly recursive. Of course, all can be implemented by using an additional stack along with the loop.

An (EDIT: better) example would be:

int f(int x) {   if( x <= 4 ) { return x; }  else { return g( x, f(x/2) ) }; }int g(int x, int y) {  // does something nasty}

Also, functional language compilers detect tail recursion and implement it whenever possible (with the additional tricks that this allows), so manually doing it becomes useless.

[Edited by - ToohrVyk on April 9, 2005 5:56:30 AM]

Illco

Apr 9, 2005 at 4:59 AM

Quote:

Yes it is, you can have pointers to objects on the stack (basically what happens when you allocate a char array on the stack in C) and can "unroll" the stack a fixed distance instead of object by object.

True. It feels a bit strange though.

Quote:

Tail-recursion is, if you look closer at its implementation, automatic loop unrolling. And some recursive functions (such as the MacCarthy 91 function) cannot be unrolled to a loop without the use of an additional stack.

Ok, I was thinking of 1-way recursion. But I presume some functions cannot be unwrapped.

Quote:

And how, exactly, does it defeat the basic idea of the current computer?

Well I thought, computers being based on a stack and all, not respecting stack conventions would be like nibbling away the basis of the whole thing. But looking at the other suggestions here, it turns out my view was too narrow.

Greetz,

Illco

ToohrVyk

Apr 9, 2005 at 5:07 AM

Quote:
Original post by auLucifer
What about if on the return trip you are adding another 1?
You won't want to just dump the whole stack there

Actually, performing an assocative operation that involves a constant can be automatically turned into a tail-recursive function too. Consider:

int syracuse(int x) {  if(x == 1) { return 0; }  if(x%2==0) { return 1 + syracuse(x/2); }  return 1 + syracuse(x*3+1);}// Can be reinterpreted automatically as:int s(c,x) {  if( x == 1 ) { return c; }  if( x%2==0 ) { return s(c+1,x/2); }  return s(c+1,x*3+1);}int syracuse(int x) { return s(0,x); }

ToohrVyk

Apr 9, 2005 at 5:14 AM

Quote:
Original post by Illco
Well I thought, computers being based on a stack and all, not respecting stack conventions would be like nibbling away the basis of the whole thing.

The machine-level stack is not the standard Computer Science stack, because there are many obvious optimizations of code that require the ability to set the stack top to a current location. This is why destroying a 10-character array at the end of scope requires as much time as destroying a 1000-character one. The internal stack of a computer allows a lot more flexibility that the plain Push/Pop/Peek primitives, and compilers are free to use it in any way they want in order to improve performance (see, for instance, O'Caml boxing and closures as an alternative to the usual C stack usage).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.