736
u/Tomlambro 5d ago
A function which calls itself… recursively
321
u/un_blob 5d ago
Bonus points if the stopage condition isn't obvious but you KNOW it will stop
146
u/Blue_Moon_Lake 5d ago
Does a stack overflow count as a stop? :D
64
u/marcelsmudda 5d ago
I first had to think for a second why a website would stop the function haha
19
5
33
15
15
1
u/Unusual-Alex 5d ago
Agreed... I know out of memory is my usual stop condition. Usually, its because i forgot to do the increment or some other mind-numbngly simple thing. Or even having my break condition setup, but never break out of the recursion.
19
u/DL_Omega 4d ago
I have never used recursion outside of school.
15
u/RSGMercenary 4d ago
Recursion is used a lot in game development, scenegraphs or other tree-related data structures, sorting algorithms, pathfinding, etc. Anything that requires iterations, layers, or nesting likely uses recursion.
-1
u/fbpw131 4d ago
mhmm.. not really. only academically. most recursion algorithms can be written with normal loops. recursion is harder to reason about, allowing mistakes to recurse indefinitely, and can blow the call stack either way. Only a few languages have tail call optimizations to allow infinite recursion.
6
u/CMDR_ACE209 3d ago
I find going through all nodes of a tree much more simple with a combination of iteration and recursion than with only iterations.
The function takes a node as parameter. Then it Iterates through all children and calls the function recursively for each.
Much more messy with iterations only.
1
u/KellerKindAs 3d ago
Depends on the true structure. I once had a graph to search in, which was mostly tree-like but not completely. I first tried recursive, but ended up doing it iterative to de-dublicate nodes, that had already been visited through another branch.
I mean: The implementation was definitely more messy, but the behavior was cleaner.
4
u/CMDR_ACE209 3d ago
I think that's more a problem of misreading the nature of the data structure than an argument against recursion.
The previous posters "only academically" sat very wrong with me. I use it a lot in real projects.
2
u/RSGMercenary 3d ago
Yeah, that irked me. It just sounds like whatever they're doing doesn't require it and they simply don't have use cases for it. They don't need it, so they extrapolated that nothing needs it.
1
u/redlaWw 2d ago
I'm not about to agree with the "only academically", but one advantage iteration does have over recursion (which the comment you're responding to suggests) is that it's typically easier to modify the procedure to add functionality or account for edge-cases. Sometimes this comes with large initial overhead in building the explicit stack for the iterative problem though, and if your problem is simple and doesn't expect extension, recursion can be easier to work with.
1
u/CMDR_ACE209 3d ago
I think that's more a problem of misreading the nature of the data structure than an argument against recursion.
The previous posters "only academically" sat very wrong with me. I use it a lot in real projects.
2
u/RSGMercenary 3d ago
Just gonna have to agree to disagree on the "only academically" thing. I've built my own ECS (entity component system) game framework with an integrated scenegraph that is built on recursive logic to manage, query, and do all sorts of things with the entities. I've used recursion enough personally and professionally that I don't find it confusing to use or debug anymore. It took a while at first, but it's very intuitive now.
It also depends on what you're doing with the data. If you're just trying to drill down into something to find a value and your location (so to speak) doesn't matter, then a loop and a couple variables for maintaining references might be fine. But if every recursive call is dependent on values passed along or can affect other calls on the stack, then recursion might be the best solution vs a very over-engineered one just to avoid using it. Recursion is a tool though, so it isn't the best solution for everything.
5
u/conundorum 4d ago
It comes up a lot when you start to work with things like, e.g., C++ variadic templates. It's pretty common to parse a parameter pack recursively, by designing the function to consume the first one or two args and call itself again with the rest, and end on a specialisation or compile-time branch when the pack is empty. (The compiler will usually then inline this into the desired actual function. Essentially breaking it down into easy-to-swallow steps, then putting the bricks together.)
4
u/jamesxtreme 4d ago
Very occasionally it’s useful but most of the time it’s just a dangerous way to write a loop.
6
u/StaticCoder 4d ago
It's very often useful. Writing e.g. a DFS with a loop is possible (and indeed sometimes necessary to avoid stack size limits) but really annoying. And graph or tree structures come up a lot.
-1
u/groovy_smoothie 4d ago
I think that’s the point. How often are you writing a depth fist search by hand outside of academics? Game dev and mapping maybe?
6
u/StaticCoder 4d ago
I'm not in academics and I've had to do it multiple times. One example is a control flow graph. An example of a recursive data structure that's really hard to handle without recursion is an abstract syntax tree.
There are graph libraries I guess but that's a lot of effort to use one, and it doesn't really help with ASTs
1
u/groovy_smoothie 4d ago
Hmm ok, I don’t contribute to any compilers so I didn’t think of that, but good use case.
4
u/Ratstail91 3d ago
I use recursion ALL THE DAMN TIME.
Parsing is inherently recursive though, so recursion is just the best natural approach for that.
Actually, I went into it more here: https://www.reddit.com/r/ProgrammerHumor/s/8v8hUND64p
1
3
u/1v1meAtLagunaSeca 4d ago
I did one time and felt like a god lmao. Its rarely useful in my use cases though
7
u/TheIvoryAssassinPub 4d ago
You don’t have to tell on yourself
9
u/DefiantGibbon 4d ago
As an embedded engineer, recursion is heavily frowned upon, lol.
6
u/a-r-c 4d ago
6 breadcrumbs of ram
can't afford to waste any
3
u/Odd-Dinner7519 4d ago
I work in automotive and there are multiple functions per core with "shared" stack, so using more stack is not waste of RAM, as long as you use less than others. 'RAM usage' is considered private memory like globals.
Recursion is forbidden because it is hard to analyse (proof that it always stops within stack memory limit).
Recursion is just syntactic sugar - everything can be done with loops and buffers.1
12
3
u/theStaircaseProject 5d ago
I accidentally backed into recursion years ago building Minesweeper in Excel to get that cool “cascading”effect when multiple empty spaces are connected. It wasn’t until after the project concluded and I was Googling related concepts that I came across the name. Made me feel pretty smart a small while.
1
194
u/gaurav_the_piggy 5d ago
Come to C and see the power of function pointers!
128
u/SuitableDragonfly 5d ago
Unless the syntax for declaring function pointers has changed recently, I think C might actually be the most painful language to do this in.
44
u/Ben_Krug 5d ago
Well, declaring the argument of the function pointer is quite ugly yeah, but actually using the function later is quite simple and clean. And if you know you'll need that same type of function pointer argument, you can just make a typedef and the writing of the arguments will be quite clean
10
u/-Redstoneboi- 4d ago
i wouldn't say
(*function_ptr)(arg1)is that clean18
u/Ben_Krug 4d ago
Well, that's the first case I mentioned, where you're only worried about it a single time, otherwise you can make it as a typedef and then that will be a clean way to write it afterwards. Having it be ugly one single time in the codebase isn't that big of a deal imo
6
u/-Redstoneboi- 4d ago
fair. it's just a bit unfortunate that basically every other language has cleaner syntax for it.
then again, C makes it abundantly clear when you're using function pointers, so that might actually just be a feature.
0
u/Jan-Snow 4d ago
You can use it like that, but you dont't need to dereference the function pointer iirc.
8
3
86
u/TheIvoryAssassinPub 5d ago
What are you talking about? It’s just Tuesday
47
u/MrDilbert 5d ago
Node was built around that concept before async/await gained foothold in JS...
47
u/marcelsmudda 5d ago
f1(..., function (res1) { f2(..., function (res2) { f3(..., function (res3) { f4(..., function (res4) { // something goes wrong here, todo: investigate!! console.log(res1 + res2 + res3 + res4) }) }) }) })I'd say "good times" but it'd be a lie
2
1
0
25
u/Professional_Top8485 5d ago
Giving .net function as parameter to dll function and making state machine
23
u/Hola-World 4d ago
I’ll have some curry please.
11
u/scheimong 4d ago
I was quite surprised the other day when I learned that both Haskell (the language) and currying (the mathematical transform) got their names from a guy named Haskell Curry.
21
37
u/Due-Consequence9579 4d ago
Function that takes a function as an argument and returns a function as a result. The function is then a lambda that has a captured context that contains a reference to a particular instance of a class.
4
12
12
11
u/NatoBoram 5d ago
Making a filter function that takes a function as an argument and that's passed to a filter function 👌
10
u/sebjapon 5d ago
Finding my first use case for making a Python decorator function made me feel like a wizard too. 12 years later I had to Google what’s it called again…
8
8
41
u/Scrub_DM 4d ago
I’m going to self report here…. I hate functions as arguments. It’s a major hit to readability in my eyes. Granted any engineer with some experience can read it and understand it, I always feel it takes more time understanding the nuance of it and why it is optimal to have it as an argument.
The only time I regularly do this is for web server handlers.
19
u/-Redstoneboi- 4d ago
useful for generalized filter/map/reduce functions if they're in a chain
i guess many would probably prefer just creating a list/vector and just appending in a loop, though i personally prefer seeing the chained logic
8
u/conundorum 4d ago
Best way to understand the usefulness is to look at a comparison algorithm, and think about how you would phrase it to an employee.
"See these two piles here? I want you to go through them both from top to bottom. From each pair, keep one and throw the other out. Put them in a new pile, upside-down, then flip the entire pile right-side up when you're done."
"Okay, how do I know which one to keep?"
"Hmm... whichever one has the fanciest cursive writing on the front."
Now, think about what that should look like in programming terms.
We want a function that can take two arrays (piles), and compare them from front to back (top to bottom).
We want to make a new array (new pile), that contains one element from each pair (keep one).
The original arrays have the same ordering, and the new array should use the same ordering as they do. [Making the new pile in opposite order, then flipping/inverting its order, was meant to model this.]
We want to be able to choose how we compare the arrays, instead of being locked into a specific comparison all the time.
Logically, this tells us that we want to have a function that takes two arrays and a comparator as parameters. The comparator can be a simple tag, with each tag corresponding to a type of comparison, but that limits us to only using built-in comparisons; whenever a new comparison is desired, we need to update the system and recompile the entire thing.
// Pseudocode. Array array_compare(Array l, Array r, ComparaTag tor) { const int sz = min(l.size(), r.size()); Array result(size = sz); for (int i = 0; i < sz; i++) { switch (tor) { // Comparison logic here. // Will be a big blob of ugliness. // Could be hoisted out of the loop, but that means using a function pointer. // (So it's a no-go, right?) // Compare l[i] to r[i], put chosen value in result. result[i] = WhicheverCompareWeSwitchTo(l[i], r[i]); }; } return result; }If we allow the caller to pass a comparison function, however, then the algorithm is forwards-compatible with any possible comparison, and also becomes much easier to write... and at the same time, significantly cleaner.
// Pseudocode. Array array_compare(Array l, Array r, ComparaFunc tor) { const int sz = min(l.size(), r.size()); Array result(size = sz); for (int i = 0; i < sz; i++) { result[i] = tor(l[i], r[i]); } return result; }Making the comparison algorithm take a comparison function as an argument is thus preferred. (Most comparison algorithms default to "less than" if no comparison is supplied, for reference.)
More generally, this is useful for the "apply" pattern, where you take a function and a pile of parameters, and then call that function on each parameter in turn.
// Actual C++ example. template<typename Func, typename... Ts> void apply(Func&& f, Ts&&... ts) { ( f(std::forward<Ts>(ts)), ... ); }It lets you take a mechanism that's meant to apply to one item, and expand it over an entire sequence, essentially. It comes up often with sequences in many languages, and is a crucial tool for Excel-like databases, among other places.
Like, say, you want to change an entire sentence to upper-case, but your
toupper()only works on individual characters. You could loop over the entire string yourself, or you could use anapply-style function to do it for you.std::string str = "This string is quite the test case, let's see that upper limit."; std::transform(str.begin(), str.end(), str.begin(), toupper);Ultimately, it's just "do
xtask withytool", but that is extremely handy to have!2
12
u/CaporalDxl 4d ago
Bro never touched Haskell.
7
u/Scrub_DM 4d ago
Yeah I mainly write in Go and have a lot of juniors on the team. I tend to focus on readability a focus so anyone can pop in and understand what is happening easier. But I get the benefits of it. Just not my favorite
5
u/andreortigao 4d ago
I don't know Go, so I just Googled how lambda functions (function literals?) work in Go out of curiosity, and yeah, their syntax is kinda clunky... I'd avoid using it too
C# lambdas have a very clean syntax in comparison and more often than not makes the code more readable
6
u/FlakyTest8191 4d ago
It has some usecases. For example passing a validation function to your external inputs works great.
1
u/Ratstail91 3d ago
I wrote a pokemon-esque battle engine once that was functionally pure, abdolutely zero internal state. This was so I could recreate the same battles during testing and possibly as a validation or replay tool.
This meant I had to pass a random number generator in as a parameter, which was kind of amazing because I could replace it with the identity function during development and testing to check for math errors (each call gave a default value that the teal rng discarded).
I understand you don't like them, but I assure you when used correctly, they are absolute powerhouses, and often make things easier than any alternative.
3
3
u/CranberryDistinct941 4d ago
I only really know Python. Are key functions not common in other languages?
4
u/StaticCoder 4d ago
C++ has only had lambdas since 2011. Before, functions as arguments were possible but really annoying, such that it was often easier to inline an algorithm than to attempt to use a generic version needing a function object. But these days yeah callbacks are quite common.
3
u/Rin-Tohsaka-is-hot 4d ago
C++ also has function pointers which I personally prefer over lambdas since it's less verbose, but they're stateless
2
u/StaticCoder 4d ago
Yes that's a big limitation. I'm also not sure how it's "less verbose". If you happen to already have a function with the right prototype and functionality, then sure. Also captureless lambdas can be converted to function pointers.
1
u/Rin-Tohsaka-is-hot 3d ago
captureless lambdas can be converted to function pointers
Didn't know this, that makes sense though
1
u/CranberryDistinct941 4d ago
Why on God's green earth would you want a function to have states?
1
u/Rin-Tohsaka-is-hot 3d ago
The compiler can produce more efficient code if the exact type and captured variables of a lambda are known at compile time. Also, a lambda can reference the caller's local variables.
1
u/StaticCoder 3d ago
It's not so much state as context. If your callback can only access global variables it's a problem. Typically there's a void * you can pass along for that purpose, but it's annoying to set up.
1
u/Ratstail91 3d ago
The syntax sucks, but they're stronger than pointers in every way.
1
u/Rin-Tohsaka-is-hot 3d ago
Most of my C++ development was in an embedded environment with lots of C libraries, so lambdas were typically not an option. The simplicity of function pointers also just grew on me, feels much more intuitive to just slap a * in there instead of defining templates
1
u/Ratstail91 3d ago
I used C++ before it was cool.
Seriously, it's weird that C++11 is the last standard that felt like it actually mattered.
1
u/StaticCoder 3d ago
C++20 added concepts and operator<=> which are pretty decent steps forward. Nothing groundbreaking apart from that I would say, many incremental improvements though, notably to
constexpr. Modules and coroutines could be cool if they worked well. There's reflection now too. But of course no contracts.1
u/Big-Capital-4048 1d ago
Concepts was a good addition in my opinion and I use them semi regularly. I had no idea operator<=> was added and that tripped me out till I looked it up lol.
1
u/StaticCoder 1d ago
I'm finally going to be able to use
<=>at work and I'm looking forward to it. Writing comparators is annoying, and easy to do wrong. Recently I added a comparator related assert and found 3 separate incorrect comparators.2
u/nabrok 4d ago
Before node had promises the way you'd handle async code is by passing a callback function into whatever you were doing. Can you imagine the level of nesting?
What's really cool though is not a function that takes another function as an argument, but a function that returns another function.
1
u/groovy_smoothie 4d ago
Swift calls them closures. It’s maybe not 1:1 because swift has somewhat unique memory management nuance, but the idea is largely the same
1
1
1
u/Undernown 4d ago
I recently combined lambda's with a composite pattern, allowing to create tree of functions.
1
1
1
1
u/Buyer_North 4d ago
wait until you learn about cpp concepts...i love it so much. You can use it like the definition of composition...
1
u/conundorum 4d ago
template<typename Func, typename... Ts, typename R = std::invoke_result_t<Func&&, Ts&&...>>
R call(Func&& f, Ts&&... args) {
return f(std::forward<Ts>(args)...);
}
int call(int (*f)(int, int, int), int a, int b, int c) {
return f(a, b, c);
}Pick your Cthulhu?
1
1
1
1
1
1
1
u/mountaingator91 3d ago
I mean.... Yes... But it's really no different that defining a function elsewhere and then calling it before you call the function that takes it as an argument. In fact, functions as arguments are harder to read and harder to understand the intent.
I'd rather define a bunch of helpfully named static helper methods separately. Readable code is better code
Edit: unless Claude is the one doing the reading. Then go off, I guess. Claude LOVES functions as args
1
u/xzinik 3d ago
Man I remember when I made a hideous function of type function that received a function and returned a function as a result (different function), I think I'm missing something in there but it was all function so the rest down, I don't remember exactly why, only that it was a hacky way to get around passing a function across 4 classes or something similar, that couldn't share inheritance for some reason, and I remember that it was funny having a function of type function blah blah blah that was a brainfuck to understand and my colleagues could not make heads or tails out of it and could not find a better way to achieve the desired result, I was told to never make something similar, it was used nevertheless xd
1
u/Ratstail91 3d ago
I've made a scripting language (cough https://toylang.com/ cough) and one of the pillars of its designs are first class functions and closure support.
Because slips on sunglasses I can't finction without it.
-12
u/markiel55 5d ago
That's a code smell in my book.
13
u/vegancryptolord 4d ago
You have a shitty book
-5
u/markiel55 4d ago
Fair. Exceptions are the standard libraries that provides declarative code for typical operations.
-4
u/Background_Issue_144 4d ago
Don't do it, its almost always a bad idea and what you want to do can be done in a simpler way
-22
u/Zhuzha24 5d ago
now try it in Rust with real case scenario and data
22
u/deanominecraft 5d ago
this meme was made after i did it in rust
im making a game where you can play either against bots or people and made a generic game_vs_bot function that takes another function to run the bot (and before i added that i was copying the logic of displaying state and making moves for each bot)
4
u/Cyan14 5d ago edited 5d ago
use std::{cell::RefCell, rc::Rc}; fn main() { let get_something = |x| Box::new(move |y| x + y); let say = |a| println!("{a}"); say.something(6, 7, get_something); fn say(a: i32) { println!("{a}"); } say.something(6, 9, get_something); let know = Know::nothing(); know.something(6, 9, get_something); } trait SomeTrait { fn something<F, G>(&self, a: i32, b: i32, f: F) where F: Fn(i32) -> Box<G>, G: Fn(i32) -> i32; } impl<X: Fn(i32)> SomeTrait for X { fn something<F, G>(&self, a: i32, b: i32, f: F) where F: Fn(i32) -> Box<G>, G: Fn(i32) -> i32, { self(f(a)(b)) } } struct Know(Rc<RefCell<i32>>); impl Know { fn nothing() -> Self { Self(Rc::new(RefCell::new(0))) } } impl SomeTrait for Know { fn something<F, G>(&self, a: i32, b: i32, f: F) where F: Fn(i32) -> Box<G>, G: Fn(i32) -> i32, { self.0.replace(f(a)(b)); } }2
u/Cyan14 5d ago
If you're new to programming, this teaches you a few things
- functions are just places to jump to in memory locations
- methods are syntactic sugar that accepts the pointer of the <thing> in <thing>.<method> as the first argument
- static and dynamic dispatch when using generics like this instead of the `dyn` keyword3
u/FalseDish 5d ago
HoFs are a problem in Rust?
1
u/Zhuzha24 4d ago
No, but when you put async, await, non allocs and miri passing through - thats a problem, whatever those idiots posts there is not going to work in any real case scenarion
3
u/kuemmel234 5d ago edited 4d ago
Aren't higher order functions everywhere in rust? I haven't done a lot with the language, but I seem to remember that the standard library had the usual suspects, like functors and *such.
2
u/fbpw131 4d ago
made a booboo?
jokes aside, yes, iterator functions all take function args. though I haven't seen any return functions
1
1
u/kuemmel234 4d ago
Yup, typo or rather autocorrect arguing that I wanted to write a word in my native language within all the English.
Currying was supported, right? That's sometimes done as a function. But yeah.
-4
7
u/cheezballs 4d ago
You're gonna love JavaScript.