A design pattern for cleaner recursive functions.
Vložit
- čas přidán 13. 05. 2024
- Patreon ➤ / jacobsorber
Courses ➤ jacobsorber.thinkific.com
Website ➤ www.jacobsorber.com
---
A design pattern for cleaner recursive functions. // A lot of new programmers struggle with their first recursive functions. This video shows you how to address one common challenge while cleaning up your code a bit.
***
Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.
About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.
More about me and what I do:
www.jacobsorber.com
people.cs.clemson.edu/~jsorber/
persist.cs.clemson.edu/
To Support the Channel:
+ like, subscribe, spread the word
+ contribute via Patreon --- [ / jacobsorber ]
Source code is also available to Patreon supporters. --- [jsorber-youtube-source.heroku...]
Here's a tip: on VS Code, one way of renaming all instances of a function or variable name is to place the cursor anywhere on the name and press F2. That feature is aware of the scope of the symbol name, so if you rename a local variable it won't affect variables with the same name on other scopes. If it's a global name, it also changes on other files where it's used.
I know freeing isn't necessary for this example, but the fact that the function allocates the buffer and just let's it hang bothers me a lot lol
Worse, the point of the program itself bothers me.
Printing numbers of a given length whose digits are in ascending order.
Yeah! You could use variable length array, like "char buffer[digits+1];", instead of malloc.
@@fusca14tube For C beginners here reading this, please never actually use VLAs until you know a lot more, especially when accepting user input. You can easily find out why on google but the gist is that the stack size is platform dependant and you could run out. Bounding the size to be safe is also nonsensical because you could have allocated a fixed array with this max to begin with.
Yeah, me too. Sorry about that. Was definitely in too much of a hurry making this one. 🤔
Speaking of free… wtb vid on arena allocation, if we are gonna stay in C anyways ❤
I think I've doing this all my life - instinctively. I tend to call these things "my internal API" - things I use often and don't want to worry about, as we say in Holland "hold up your own pants". For that reason I would have just returned "buffer" and let the "helper function" do the printing. For I might want to use that thing for entirely different purposes. I would also add "free()" to the "helper" function - "hold up your own pants". The whole thing has a lot to do with DRY and factoring in general IMHO. It is not merely restricted to recursive functions.
Totally agree, with the given example the need is "compute for given lenght", that's the public contract (our API / interface), having a facade delegating to the right implementation is the right thing to do, otherwise 1) everyone calling the function has to pass boilerplates arguments (implem details leak) and its annoying, 2) when switching to an iterative implementation you'll have a lot more changes to do. Even in C encapsulation and SRP apply: entry point provides public interface, while recursive function provides actual computation.
Long time Jacob, glad to see you back making videos.
Glad to be back. Hopefully, I'll be able to get back into a rhythm.
I'm not sure of the exact pros and cons for this example, but an alternative implementation that comes to mind would be to use static variables directly inside the function, as these stick around for future calls.
The only thing to watch out for is that these need to be reset for every fresh run of the function. A counter to track the number of active recursions might be sufficient (+1 at the beginning of the function and -1 at the end) could help with this. Otherwise if you already know what the final run of the function is, i.e. you already have some logic that only runs at the very end of the recursion then you can just reset any statics then and there.
You forgot to call free! Hahaha, nice video as always
Yep. 😖
Jacob, thank you for your great work.
Could you make a video about #line directive.
When it may be needed and the nuances it involves.
Welcome back Jacob, good to see you again, I missed my C guru!
Sir big fan of yours❣️you are such a nice sensie🥰
sure, and in the wrapper printStringInc() you can now use the VLA feature or alloca() to allocate stack space to *buffer instead of using heap with calloc().
the recursive function can also be marked as static to ensure its not called from any other translation unit
can you exclude it from the header file to make it private?
Hi, long time, Welcome Back.
Unrelated, but what's the point of the `offset` variable exactly? Couldn't you just do `buffer+1`?
Yes. You could.
No, because you print the buffer at the end.
When you do buffer + 1, you lose the address where the buffer starts, i.e., you don't know anymore where your string starts
Your new function *barely* slows anything down, because tail call optimization.
This is a bug. It should not be tail call optimizable; you are missing a line after the call to the _rec function.
But this is OBVIOUS! Moreover, I'd be also moving "printf" and "free" calls to the wrapper function.
BTW, FedEx lost my "malloc" shirts from you merch store.
Well... Well explained except for 1 thing: this is not recursion but iteration, which is a form of recursion but doesn't really.
Ouch, that leak 😂
Yes, indeed.
He's gonna say make a recursive helper isn't he
I think the main problem with this example is that it's a toy example. While it's more difficult for a newbie to understand, you should use quick sort as the example of writing a recursive function. The sad reality is that 99% of all recursively implemented functions would be better off and easier to implement and understand if they were iterative instead, but quick sort is one of those few that actually is easier to understand when written recursively. However, that said, it'd be better to demonstrate how to convert from recursion to iteration.
Personally, I reject recursion as a viable methodology. I've got a lot of reasons for why, and it would take more than a single comment to explain why, but the biggest is that in 99% of cases it's just easier to understand plain iteration.
whoah, atoi()
Eh... double inderection can really hurt performance. I'd probably implement the outer function as a macro instead. That way the inner workings are still abstracted away, but the performance is the same as without it
Indirection matters more when its called for every iteration, here the delegation is only called once, a'd it's way cleaner, one function to provide public API (with no boilerplates arguments), and the other one doing actual computation. For 1000 iteration we only have 1 extra function call, drawback is ridiculous compared to the advantages
@@adriencuisse9641 sure, but using a macro has the exact same advantages, while also removing the drawback, so why make something knowingly worse?
I would avoid macros because problems are easier to detect & fix with code, but that's a matter of opinion I guess. I would rather not use preprocessor for this concern, but its OK if macros are well dosed and not the convention
You can create a whole codebase with macros, but it Will become hell. Exagerating on purpise, but I've put my limit as "dont use macro if its not conditional inclusion, constant definition or platform related stuff", that's Just a personal convention, you're 100% free to have your own.
@@adriencuisse9641 I agree that macro hell can be a problem. I would just personally add wrapper functions to that list. Or use an other language like Zig which has a way better compile time environment (including e.g. specifying that the inner function should be called inline)
Could you please try speaking a little slowly? I think your lectures are excellent but the dialog delivery is a tad fast.
@01:30 "Next there's this offset. This tells me where I am in the current number..."
Wrong. You are a human being, and the C source code "executes" on an abstract machine.
I would suggest that you, as an instructor, refrain from using personal pronouns when talking about the meaning and flow of source code.
"Next there's this offset. The variable offset keeps track of where how far along yadda-yadda-yadda..."
Do not attach yourself to code that is being developed. Otherwise, programs will be viewed as "alive" and, of their own volition, triggering your exhilaration or frustration.
Code is an object. Stop inducting beginners to mystically "become one with the code" and "take it personally" when "they and their code" fail to perform as desired.
You, and your students, live and breathe in the real world. Tron was just a fictional movie.
Rule of thumb for recursive functions: Don't use recursive functions.
To iterate is human, to recurse divine.
Horrible. Instead of one function, you now have two. With zero encapsulation. If this is the best you can do with C, don't use C.
there’s a whole scary world out there that isn’t OO - and it actually works 🙀
Hopefully, one day C will have proper nested functions, like Algol had ... in 1960! 😂 (I know GNU C has them as an extension, and I do use them.)
Write static inline and pray