A design pattern for cleaner recursive functions.

Подписаться 158 тыс.

Просмотров 5 тыс.

50% 1

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...]

Опубликовано:

13 май 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 51

@tiagobecerrapaolini3812 18 дней назад

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.

@SouravTechLabs 3 дня назад

I like the fact that he doesn't notice the typo "PrintStringInc" while making the video!

@awesomedavid2012 18 дней назад

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

@unperrier5998 18 дней назад

Worse, the point of the program itself bothers me. Printing numbers of a given length whose digits are in ascending order.

@fusca14tube 18 дней назад

Yeah! You could use variable length array, like "char buffer[digits+1];", instead of malloc.

@lMoonHawk 18 дней назад

@@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.

@JacobSorber 18 дней назад

Yeah, me too. Sorry about that. Was definitely in too much of a hurry making this one. 🤔

@JustinCromer 18 дней назад

Speaking of free… wtb vid on arena allocation, if we are gonna stay in C anyways ❤

@unperrier5998 18 дней назад

Long time Jacob, glad to see you back making videos.

@JacobSorber 18 дней назад

Glad to be back. Hopefully, I'll be able to get back into a rhythm.

@HansBezemer 18 дней назад

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.

@adriencuisse9641 18 дней назад

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.

@Timmyfox 18 дней назад

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.

@LogicEu 18 дней назад

You forgot to call free! Hahaha, nice video as always

@JacobSorber 18 дней назад

Yep. 😖

@jazzycoder 18 дней назад

Welcome back Jacob, good to see you again, I missed my C guru!

@aayan4885 18 дней назад

Sir big fan of yours❣️you are such a nice sensie🥰

@__hannibaalbarca__ 18 дней назад

Hi, long time, Welcome Back.

@xxFurjisxx 10 дней назад

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.

@angelcaru 18 дней назад

Unrelated, but what's the point of the `offset` variable exactly? Couldn't you just do `buffer+1`?

@casperes0912 18 дней назад

Yes. You could.

@Thwy 18 дней назад

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

@dimitrioskalfakis 18 дней назад

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().

@MrTrollland 17 дней назад

the recursive function can also be marked as static to ensure its not called from any other translation unit

@natterbrot 17 дней назад

can you exclude it from the header file to make it private?

@danielrhouck 18 дней назад

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.

@m0Ray79 18 дней назад

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.

@GooogleGoglee 18 дней назад

Well... Well explained except for 1 thing: this is not recursion but iteration, which is a form of recursion but doesn't really.

@guc9ugjvobovov526 День назад

Whats the context

@leokiller123able 18 дней назад

Ouch, that leak 😂

@JacobSorber 18 дней назад

Yes, indeed.

@KirkWaiblinger 18 дней назад

He's gonna say make a recursive helper isn't he

@SavageScientist 18 дней назад

whoah, atoi()

@anon_y_mousse 15 дней назад

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.

@TheyCallMeHacked 18 дней назад

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

@adriencuisse9641 18 дней назад

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

@TheyCallMeHacked 18 дней назад

@@adriencuisse9641 sure, but using a macro has the exact same advantages, while also removing the drawback, so why make something knowingly worse?

@adriencuisse9641 18 дней назад

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

@adriencuisse9641 18 дней назад

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.

@TheyCallMeHacked 18 дней назад

@@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)

@anirudhdattatri 11 дней назад

Could you please try speaking a little slowly? I think your lectures are excellent but the dialog delivery is a tad fast.

@rustycherkas8229 17 дней назад

@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.