A question about stack memory using recursion functions

[pdgui]

Hi,

I'm reading this interesting C tutorial:
http://sundog97.tripod.com/tutorial_c/chap05.html

Here it explains the use of stack memory when used recursion functions,
and made me ask about if the use of recursion like as loop function, make this function fast compared if I used a FOR or WHILE loop

[Skillless]

Are you asking whats faster, a recursive function or a loop?

[EverBeginner]

High!

The memory in stock is flat till re-assigning a task in the given frame until the end. That is the re-enterability. Uninterrupted.
The only difference is a speed of the return while in a loop.
The recursion is an approach to tackle otherwise intact pile of problems.

[moorecm]

Although the stack is fast memory, iterative solutions that do not require caching a stack frame are [always?] faster. Recursive functions are often shorter and easier to implement than their iterative couterpart but they do have their costs.

[pdgui]

Are you asking whats faster, a recursive function or a loop?

I asked if a recursive function with same conceptual function as WHILE/FOR loop, is faster then use directly WHILE/FOR

The recursion is an approach to tackle otherwise intact pile of problems.

Recursive functions are often shorter and easier to implement than their iterative couterpart but they do have their costs

could you pass me references (bibliography) on this? :)
I'm studying C/C++ for Audio/DSP,
and make softwares stable/fast is my actual problem...
I think that a reflection about use (or not) of Recursive functions is the way... (?)

Thanks!

[dserbia]

Definitely use iterative.
Recursive functions are:
1) Slower (they have to copy the parameters to the stack on every call)
2) You may run out of stack memory and cause the program to crash.

I have written a simple program to test this. It sums all the numbers from 0 to MAX first using a recursive for-loop, and then a "standard" iterative for-loop. Here is the code:

#include <iostream>
#include <time.h>
#define MAX 100000

using namespace std;

int sum;
void for_recursive(int i, int max)
{
    if(i > max) return;
    sum += i;
    for_recursive(i+1,max);
}

int main()
{
    sum = 0;
    clock_t start = clock();
    for_recursive(0,MAX);
    printf("\nRecursive for-loop running time: %.4f\n",(float)(clock() - start) / CLOCKS_PER_SEC);
    sum = 0;
    start = clock();
    for(int i = 0; i <= MAX; i++) sum += i;
    printf("\Iterative for-loop running time: %.4f\n",(float)(clock() - start) / CLOCKS_PER_SEC);
    return 0;
}

Under Windows 7 with a 1.86 GHz processor and 3 GB RAM, compiled using MinGW the results are following:
Run 1, MAX = 10 000:
Recursive: 0.0000
Iterative: 0.0000
Run 2, MAX = 100 000:
Recursive: 0.0020
Iterative: 0.0000
Run 3, MAX = 1 000 000:
Recursive: Ran out of stack
Iterative: 0.0030
All times are in seconds.

Iterative functions are obviously faster and much more stable than recursion. Recursion should be used only when it is impossible or more complicated to do the same operation iteratively.

Hope I helped.

[pdgui]

Thanks dserbia;

I think a complete understand will be a process :)
But this code clarified some doubts;

Thanks!

[Disch]

To this day I still don't understand why recursion is taught in introductory C++ (or any introductory programming) courses and tutorials. It really has no place in any introductory situation.

Often times the examples of recursion that they teach are things you should never do... so it really does nothing but teach horrible practice.

[EverBeginner]

Hello pdgui,

Here it is as requested.
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/algor_complete.html

Please note it will not help without knowing an application process because of the needless recursion cause.

[pdgui]

This message is still question on recursion, but
in pre-processor directives...

I'm studying string.h; in line 35-39

#ifndef _SSP_STRING_H
#define _SSP_STRING_H 1

#include <ssp.h>
#include_next <string.h> 

and in ssp.h:

#if __SSP_FORTIFY_LEVEL > 0
# include <stddef.h> 

Why recall a header file that recalls the previous?

[EverBeginner]

Well, this is probably to narrow a scope of the application header.
In my opinion if this appoach had done it then the one that took the
risk knew the score in advance. Perhaps nothing else appeared to be in
vicinity.
As far as I have been introduced to the area there is no compiler known
that could get out of such a recollection.

[Skillless]

EverBeginner,

youre a really good poet

[pdgui]

EverBegginer thanks for
link and questions...
I apologize for the last question:

there is no compiler known
that could get out of such a recollection.

In the file string.h, the initial comments are:

/*This file is part of GCC*/

therefore means that is possible that other compilers
(from others OS) have other "string.h" (I'm using
Xcodes/OSX), and other method of implementation of
these directives (without make recollection?)

thanks :)

[pdgui]

Sorry,
the last thread is about stdio.h, not string.h :S

[EverBeginner]

Every OS may extend the C/C+ for something or vice versa. I don't know.
Although to use a compiler in such a way one
has to know the point in the entire file.
It would be quite costly for me if I were in charge.

not at all

[Skillless]

So deep.