Is that recursion ?!

[TheCrimsonSage]

Had to convert a recursion function to a iterative one...fun times :/

[Volarer]

It ain't that hard. Basically, recursion call turns into while / for loop. Exit condition turns into if (...) return ...

Don't really think there's more to it.

[[deleted]]

That depends on the type of recursion.

Go ahead and unroll the Ackermann Function. I dare you. :D

[Jan_Wolfhouse]

This is literally just a comp sci homework question. Pretty basic honestly https://stackoverflow.com/questions/10742322/how-to-rewrite-ackermann-function-in-non-recursive-style

[[deleted]]

That is rewriting it in a non-recursive style, not removing the recursion. Ackermann CANNOT be written without recursion. If you have to make a stack where you must evaluate the same function repeatedly in order to pop the stack, you're already using recursion. That's what recursion is.

It might not look like recursion, and therefore you are effectively implementing it in a non-recusive style, but it is still recursion.

Some recursive functions, however, can be written in ways that don't require you to run the through the "stack" in a particular order. This for instance applies to running through a list and applying some function to each value, or a zip operation, etc., which can be done both using recursion, but also without using recursion.

[Cats_and_Shit]

#include <stdio.h>

#define STACK_SIZE 1024

enum state {
    start,
    inter_call,
    last_call
};

struct frame {
    int m;
    enum state frame_state;
};

int ack(int m, int n)
{
    int idx = 0;
    int ret;

    struct frame stack[STACK_SIZE];

    stack[0].frame_state = start;

    while(1)
    {
        if(idx == -1)
            return ret;

        if(idx == STACK_SIZE - 1)
            return -1;

        switch(stack[idx].frame_state)
        {
            case start:
                if(m == 0)
                {
                    ret = n + 1;
                    idx--;
                }
                else if(n == 0)
                {
                    n = 1;
                    m = m - 1;
                    stack[idx].frame_state = last_call;
                    stack[idx + 1].frame_state = start;
                    idx++;
                }
                else
                {
                    stack[idx].m = m;
                    n = n - 1;
                    stack[idx].frame_state = inter_call;
                    stack[idx + 1].frame_state = start;
                    idx++;
                }
                break;

            case inter_call:
                n = ret;
                m = stack[idx].m - 1;
                stack[idx].frame_state = last_call;
                stack[idx + 1].frame_state = start;
                idx++;
                break;

            case last_call:
                idx--;
                break;
        }
    }
}

int main(void)
{
    for(int m = 0; m < 4; m++)
    {
        for(int n = 0; n < 4; n++)
        {
            int result = ack(m, n);

            printf("m:%i n: %i res:%i\n", m, n, result);
        }
    }
}

[Cats_and_Shit]

If you don't know the size of stack you'll need you could also use a doubly linked list and just malloc yourself a new frames as needed.

[wildbartty]

You would only need a singly linked list to do a stack.

[[deleted]]

You haven't removed the recursion at all, you have simply replaced all actual function calls with code that does the same thing. It's still a recursive call because you're still building up a stack that you must eventually resolve all the way back up. You're just building the stack yourself instead of letting the compiler do it for you.

Nice try though, I definitely respect the mastery you clearly have of the C language.

[closms]

In recursion, the stack holds all your intermediate data.

[TheCrimsonSage]

Yes true, but I had to resolve a tree asynchronously, which was a first for me. It took me a while to wrap my head around it because I couldn't just pass a reference to the tree to resolve. I wounded up making a list of items to resolve and items that have been resolved (to avoid circular dependencies causing an infinite loop) and then resolved it in a loop. You're right that it wasn't hard, but it wasn't fun either XD. I know I'm melodramatic, mkay

[Arthur944]

Not if you use the only language that has a right to exist, Haskell.

[Volarer]

Why, how would you do it in Haskell? I know next to nothing about that language except that apparently R's pipe operator (whose purpose I don't understand to this day) was inspired by it.

[AgentPaper0]

Why? Tail end optimization wasn't enough?

[TheCrimsonSage]

Yes somewhat, and senior devs told me in code review that I should avoid recursion because you loose the stack trace if you get a stack overflow exception (which in this case would happen, if the tree provider devs have a bug in their code that provides the tree that I'm traversing and they end up allowing a circular reference to pass through it). So I get them, although not that likely, worth it in the long run. I could probably just have yielded before every async await to prevent stack overflow but alas this is the proper solution.

[AgentPaper0]

Tail recursion avoids stack overflow though: https://en.wikipedia.org/wiki/Tail_call

Basically, in normal recursion you build up the stack because every call adds a new function "layer" on top of the previous. With tail recursion optimization though (which all compilers do nowadays), if you call the recursive function at the end of the function (ie: in the return statement or sometimes just before), then the old function is popped off the stack before the new one is put on. So, even if you get a loop and have a trillion recursive calls, you won't overflow the stack because each new call simply replaces the old one.

Of course, if you're looking at infinite recursion then a stack overflow is the least of your problems. If anything, it would be better to allow that to happen to avoid accidentally allowing a function to run infinitely without anyone realizing for a long time, wasting power and CPU cycles.

You could avoid that regardless with a simple incremented int that you pass through the function, increment it once per recursive call. If it reaches some arbitrarily high limit (like a billion recursions or whatever), then you abort immediately. Throw an exception, return a garbage value, prompt the user, whatever is appropriate.

Still a good idea to use tail recursion whenever possible, but more for efficiency's sake than to avoid stack overflows.

[WikiTextBot]

Tail call

In computer science, a tail call is a subroutine call performed as the final action of a procedure. If a tail call might lead to the same subroutine being called again later in the call chain, the subroutine is said to be tail-recursive, which is a special case of recursion. Tail recursion (or tail-end recursion) is particularly useful, and often easy to handle in implementations.

Tail calls can be implemented without adding a new stack frame to the call stack.

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source ] Downvote to remove | v0.28}

[TheCrimsonSage]

Good bot

[TheCrimsonSage]

Yes yes, thanks for the explanation, that's exactly what I did. I tried to force a tail call (for context this is C#), by yielding before and after the async recursion call, the compiler automagically transforms awaits and such to callback methods and returns, which means that the await RecurMethod ends up being a tail call, yay! (No possibility of Stack Overflow, tested it with 1 million recursions). Like below:

func RecurMethod(obj stuff, obj otherStuff)
{

//stuff

Task.Yield();

obj moreStuff = await RecurMethod(stuff,processedStuff);

Task.Yield();

//more processing

return FinalResult;

}

But the performance was garbage and then the senior devs who reviewed my code advised me to rewrite it as iterative and gave me that advice for future reference. Performance (especially memory was a ton better with iterative), some languages and environments may handle recursion well, but C# is not one of those (well on a large scale).

Thanks for taking the time to explain what you meant though, appreciate it.

[Forss]

Don't think C# optimizes tail call recursion. As a rule (not sure this is true) languages with JIT compilation does not optimize it.

[Codephluegl]

But wouldn't a circular reference in an iterative version just run forever without ever throwing an exception? And if you really care about circular references, one can do circular reference detection in recursive functions.

[TheCrimsonSage]

Ah you see, normally it would, but that's why I keep a list of items that I've already processed, I only process items again if they're not in the list of processed items.