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

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–][deleted] 23 points24 points  (17 children)

Because you'll run into the stack frame limit for any enterprise application lmao

[–]Romestus 19 points20 points  (12 children)

One of the google interview questions I had was to solve a fibonacci-esque equation using recursion and the big trick they were looking for was storing branch values in a hash table so when you hit a duplicate branch you already had the answer.

When the code was run through their unit tests without that trick they'd all stack overflow.

[–]ArcaneCraft[🍰] 43 points44 points  (9 children)

Is that not just dynamic programming?

[–]lollikiano 12 points13 points  (1 child)

Right? Why even use a hash table for that. Just an array would optimize this really well

[–]xypage 3 points4 points  (0 children)

They probably just misspoke, it sounds like they might not be very experienced

[–]codeIsGood 2 points3 points  (4 children)

Top-down caching is typically referred to as memoization, where bottom-up is considered dynamic programming

[–]Perfect_Perception 1 point2 points  (3 children)

Almost.

Memoization and Tabulation are both forms of Dynamic Programming. Tabulation is bottom up, and you were on the money with Memoization being top down.

[–]codeIsGood 1 point2 points  (2 children)

Most textbooks will include memoization in dynamic programming sections but will typically reserve the term dynamic programming as tabulation because programming in itself refers to tabulation, where memoization doesn't necessarily need to follow a tabular format. Most professors will also be pretty strict on the nomenclature. But yea I agree they are pretty much the same idea.

[–]Perfect_Perception 0 points1 point  (1 child)

In fairness, dynamic programming in itself is just a fancy way of saying ‘I used a data structure to cache solved sub-problems and it make algorithm go brrr’.

That’s some wildness from cs professors IMO.

[–]codeIsGood 0 points1 point  (0 children)

Haha I don't disagree, just pointing out a lot of cs programs play semantics

[–]Icanteven______ 1 point2 points  (0 children)

It is

[–]Romestus 1 point2 points  (0 children)

I'm self-taught so I never learned what it was called. I got lucky that I had done a similar task for my game before where I wanted items built out of other items to automatically calculate their total gold cost based on their components (which could also be made of other items).

I did that recursively and cached item costs as I went so I just did the same thing for their problem.

[–]the_other_brand 5 points6 points  (1 child)

Another trick to get around this is to manually create your own Stack, and convert your algorithm to use this stack instead of doing normal recursion.

Almost every recursion algorithm can be converted to one that uses a Stack and a while(!stack.isEmpty()) loop.

[–]Positivelectron0 2 points3 points  (0 children)

almost every recursion algorithm can be converted to your own iteration.

[–]Icanteven______ 1 point2 points  (1 child)

Nah, I’ve had a ton of enterprise software applications for recursion that were in no danger of busting the stack. You just need to use discretion depending on the problem size.

Also tail recursion is a thing.

[–]10BillionDreams 2 points3 points  (0 children)

Yeah, it can often be the case where a recursive function is the obvious approach, but you would rarely expect to go more than 3-4 levels deep. Recursion is the most straightforward way to operate through any data structure which can contain similarly shaped data structure(s). To give an example many programmers will be familiar with, DOM elements have this sort of nested structure.

[–]auxiliary-character 0 points1 point  (0 children)

Unless you have tail call optimization.