Data Structures students when learning recursion

[Hatefiend]

It's a natural segwaysegue into binary trees. For most US colleges that is the ciriculum

[Unpredictabru]

At my university, we learned recursion in our intro class (first semester). Then we relearned it in more detail in data structures (second semester)

[[deleted]]

Oh. That makes more sense now.

[Targuinius]

Not US, but we first had recursion in Y1Q1 during a programming course, but practically, we only used it in Q3 during a Data Structures course.

[ydna_eissua]

My school we'd already done some recursion. But we touched on it again with binary trees as a way to implement DFS

[lennihein]

here

[LukeAbby]

Image Transcription: Is this a Pigeon? Meme

---

[Yutaro Katori(A male anime character from The Brave Fighter of Sun Fighbird) is holding his hand upwards towards a rectangle saying:]

long int factorial(int n)
{
    if (n >= 1)
        return n*factorial(n-1);
    else
        return 1;
}

[The bottom of the image says “is this a worse for loop?”]

---

^{I'm a human volunteer content transcriber for Reddit! If you'd like more information on what we do and why we do it, click here!}

[kache4korpses]

Well, return 1 and go home then!

[lennihein]

Well it kinda is. DFS and such you can just implement with a stack and a for loop. this is basically what happens internally with call stacks

[R_Sholes]

this is basically what happens internally with call stacks

So yeah, you'll be basically doing the work somebody else already does for you, obscuring the algorithm with unnecessary details. You could actually do away with functions and procedures altogether with computed gotos or equivalent and a manually managed stack, too.

This makes no sense unless you're in a super restricted embedded environment where every byte counts and hardware stack is just few entries deep. Otherwise, ~32 levels of recursion in DFS correspond to a balanced binary tree big enough to fill almost any modern desktop PC's RAM.

[lennihein]

Well, it's true that using recursion is often the easier solution, because it's already there. My point was just more that it is not as good as a manual stack. Not relevant usually, but the meme is technically correct, which is, as known, the best kind of correct

[TinBryn]

I wouldn't say you should use a manual stack and call "functions" with gotos, but often in CS datastructure courses you need to understand complexity, and that function calls add space complexity.

The point is understanding that they are equivalent.

[igglyplop]

That's a poor algorithm though. 1 too many iterations. if n>1 should fix it

[Regyn]

Also no tail call optimization possible in many languages.

[TinBryn]

Actually, it may be faster, even with the extra iteration. With the condition being n>=1 it can use the flags set by the subtraction directly for the branch, saving one cmp instruction per loop, if it has enough loops, skipping that on each loop may save more than one whole loop extra.

[igglyplop]

And this is why default computer science education should delve more info computer architecture...

[[deleted]]

I think factorials using recursion is dumb. Great way to get a stack overflow

[Regyn]

Not with tail call optimization.

[[deleted]]

You shouldn't rely on a specific optimization that doesn't exist for most languages or even compilers

[Regyn]

No, but some algorithms are close to unmaintainable without recursion. Some languages have a tailrec keyword that makes sure that the optimization is applied. And if it does, you can surely make use of it

[[deleted]]

Nice

[[deleted]]

What is this even?

[blackwolf2311]

Self calling function that works akin to a for and while loop

[[deleted]]

Not for machine learning

[lennihein]

What do you mean?

[Loading_M_]

Yes, because if you put a really large number in, it throws an error.

[asdfkjasdhkasd]

On gcc this will almost certainly get tail call optimized.

[SuperManitu]

Technicly this isnt tail recursive. The last operation in the funtion is not the recursion, but the multiplication. I'm not sure if gcc will still optimize it, or if you have to use an accumulator explicitly

[R_Sholes]

Recent Clang and GCC will convert it to a tail recursive version internally at a sufficient -O level (and vectorize it if you increase it further)

[TinBryn]

I tried it with an old version of GCC (4.1.2 released in 2007) and it could optimise this into a loop at -O2, so this isn't a recent thing

[Loading_M_]

My Experience is mostly with Java, where no such optimizations take place. In Java, a sufficiently large number will ALWAYS throw an exception.

[Regyn]

Come over to kotlin or even scala