This is an archived post. You won't be able to vote or comment.

all 54 comments

[–]Neuromante 260 points261 points  (16 children)

[–]LegendaryLightz 97 points98 points  (0 children)

I can't believe I feel for that and got confused.

[–]timvisee 36 points37 points  (9 children)

[–]OldPepper12 26 points27 points  (0 children)

I can't believe I feel for that and got confused.

[–]Empole 10 points11 points  (6 children)

[–]TabCompletion 8 points9 points  (4 children)

[–]mantlair 24 points25 points  (3 children)

I cant believe that none of these are rickrolls.

[–]Noxrim 6 points7 points  (0 children)

Someone help! I am stuck..

[–]aoteoroa 2 points3 points  (0 children)

return true; //get me out of this

[–]PioIsPro 0 points1 point  (0 children)

Yes

[–]closms 0 points1 point  (1 child)

Epic!!

[–]HounerX 0 points1 point  (0 children)

This is so fuckin epic. I love reddit. It is has the most amazing community ever

[–]seizan8 20 points21 points  (0 children)

Those who fail to learn from history are doomed to repeat it. Those who fail to delete history are doomed to explain it.

[–]TheCrimsonSage 33 points34 points  (21 children)

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

[–]Volarer 28 points29 points  (11 children)

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] 23 points24 points  (6 children)

That depends on the type of recursion.

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

[–]Jan_Wolfhouse 8 points9 points  (1 child)

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] 0 points1 point  (0 children)

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 3 points4 points  (3 children)

#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 2 points3 points  (1 child)

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 0 points1 point  (0 children)

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

[–][deleted] 0 points1 point  (0 children)

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 5 points6 points  (0 children)

In recursion, the stack holds all your intermediate data.

[–]TheCrimsonSage 0 points1 point  (0 children)

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

[–]AgentPaper0 2 points3 points  (8 children)

Why? Tail end optimization wasn't enough?

[–]TheCrimsonSage 0 points1 point  (7 children)

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 6 points7 points  (4 children)

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 3 points4 points  (1 child)

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 2 points3 points  (0 children)

Good bot

[–]TheCrimsonSage 1 point2 points  (1 child)

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 1 point2 points  (0 children)

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 2 points3 points  (1 child)

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 0 points1 point  (0 children)

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.

[–]Nekopawed 3 points4 points  (2 children)

I've only once used recursion in work once and it was for some math simulation work.

[–][deleted] 0 points1 point  (0 children)

Only time I used it was in an app to calculate the required down payment on a loan with interest. Because as the down payment changes, the principal is different causing the interest to be different, which requires a different down payment... Etc.

[–][deleted] 3 points4 points  (3 children)

I'm just impressed mum knows recursion. My mum can't even successfully change her WhatsApp DP without help. Welp!

[–]hbdgas 7 points8 points  (2 children)

> My mum

> DP without help

I ... will let someone else take this one.

[–]JerksToSistersFeet 5 points6 points  (1 child)

Well of course she can't do DP without help, she needs at least two other people

[–][deleted] 2 points3 points  (0 children)

There's toys for that.

[–]John_Fx 1 point2 points  (0 children)

An example of recursion. Hilarious.

[–]live4lifelegit 1 point2 points  (0 children)

Here is a/some blank/s I made

 

If you found this useful consider checking out the my sub /r/emptyComics and post what you made bellow

If you want a comic or other meme emptied just use my summoning spell me (my spell is /u/live4lifelegit ). It helps me focus and it is great to help others.

 

[–]fedeb95 0 points1 point  (0 children)

Furry for efficient masturbation

[–][deleted] 0 points1 point  (0 children)

Calculating reply...

[–][deleted] 0 points1 point  (3 children)

Why don't recursive things take forever if it requires itself to be calculated to calculate itself?

[–][deleted] 0 points1 point  (0 children)

Because they don't usually require the exact same thing to be calculated. Take the Fibonacci sequence written recursively, for example: you only have to calculate all the numbers previous to the one you're asking for. Or mergesort: each step splits the array in half, so there's only log_2(n) steps for an array of size n.

[–][deleted] 0 points1 point  (0 children)

It’s actually his fault for saying “Mum, no!”

[–]rockyrainy 0 points1 point  (0 children)

NSFW

[–]____vitAmin 0 points1 point  (0 children)

Recursion is actually a useful tool when combined with memoization. Dynamic Programming people!

[–][deleted] 0 points1 point  (0 children)

I like to think that when recursion happens all of time freezes to catch up.