CODEWITHSUNDEEP
recursionstack
RAY66
RAY66

Reputation: 35

Isn't using a stack same as recursion?

When asked for a non-recursive algorithm to solve a problem, people often use stacks but in essence aren't stacks and recursion same?. Moreover, the space complexity remains the same(asymptotically) when stacks are used to replace recursion. Is there any fundamental difference that I have failed to observe?

Upvotes: 1

Views: 76

Answers (3)

Sylwester
Sylwester

Reputation: 48745

Yes, it's the exact same thing.

Using a Stack instead of using the call stack is either a work around (when a language has less stack space than the maximum your program needs to handle) or it's a optimization that might save some space since the stack frame usually take some machine words in languages that doesn't do TCO or you don't need to store the data the same way so it makes the total consumption far less even when the stack is less space efficient per item.

Not all languages need it though, In the language Racket it doesn't serve any purpose to use an explicit stack since there is no limit on the stack since other than the total memory the program has so even with non TCO calls (like tree traversal) it still would work until all memory is consumed.

In Java the stack space is configurable when you start up your program. It prefer to read recursive code so check if your language can do that before reverting to using an explicit stack.

Upvotes: 0

Billy ONeal
Billy ONeal

Reputation: 106549

Big-O complexity may be the same in some cases, but constant factors using an explicit stack are often better. Moreover, the size of the machine execution stack is often relatively small, while an explicit (heap-allocated) stack can grow much larger.

Sometimes you'll want to look for a completely different algorithm that happens to be non-recursive that will perform much better. Consider the naive fibonacci sequence algorithm:

int f(int n)
{
    if (n < 2)
    {
         return 1;
    }

    return f(n-2) + f(n-1);
}

This algorithm takes exponential time :(

The non-recursive version (actually a form of "dynamic programming" in this case) is only linear in n, and does not use a stack:

int f(int n)
{
    int fMinusOne = 1;
    int fMinusTwo = 1;
    for (int idx = 1; idx < n; ++idx)
    {
        int next = fMinusOne + fMinusTwo;
        fMinusTwo = fMinusOne;
        fMinusOne = next;
    }

    return fMinusOne;
}

Upvotes: 0

ifyalciner
ifyalciner

Reputation: 1248

Your applications stack size is more limited than the data structure stack. As long as you can allocate memory dynamically (actually this time it depends on applications heap) you will have no problem.

Your applications stack as mentioned is more limited plus that it has the copy of each temporary local variable, function parameters, return values, stack pointers and ext. That makes its size more reduced than it seems.

Upvotes: 1

Related Questions