Stack is slow than heap?

[Cholo Lennon]

You probably use them all the time, even without realizing. (Quicksort
is a recursive algorithm, and std::sort() usually uses introspective sort,
which uses quicksort as one of its steps.)

I use them from time to time when I need to implement algorithms which
are very recursive in nature. Often implementing them non-recursively
makes the implementation significantly more complicated (and usually
longer) than the recursive version.

Just a comment: Al least in VC++, qsort is implemented for performance
reasons without recursion (well, it use recursion, but using goto and
some stack manipulation)

Regards

 

[Jorgen Grahn]

You probably use them all the time, even without realizing.

Well, I assumed we were talking about "use" as in "write code which
does recursion".

(Quicksort
is a recursive algorithm, and std::sort() usually uses introspective sort,
which uses quicksort as one of its steps.)

I use them from time to time when I need to implement algorithms which
are very recursive in nature. Often implementing them non-recursively
makes the implementation significantly more complicated (and usually
longer) than the recursive version.

I've seen how elegant recursive code can be: my CS education was about
50% functional programming. I should probably use it more often --
but I'd watch out for extreme stack usage.

/Jorgen

 

[Juha Nieminen]

Just a comment: Al least in VC++, qsort is implemented for performance
reasons without recursion (well, it use recursion, but using goto and
some stack manipulation)

Technically speaking an algorithm does not become "non-recursive" simply
because it has been implemented without a call to the current function.
It's recursive if it needs a stack whose size depends on the amount of
input. Usually the easiest way to implement this is to simply make the
implementation literally recursive.

 

[gwowen]

  Technically speaking an algorithm does not become "non-recursive" simply
because it has been implemented without a call to the current function.
It's recursive if it needs a stack whose size depends on the amount of
input. Usually the easiest way to implement this is to simply make the
implementation literally recursive.

So consider the following two C99 functions:
void
f1(const int input[], size_t N)
{
int scratch[N];
frob(int,scratch,N);
return;
}

void
f2(const int input[],size_t N)
{
int *scratch = malloc(N * sizeof(int)); // null check elided
frob(input,scratch,N);
free (array);
return;
}

Are you suggesting that f1 is recursive and f2 is not?