Learning DSA, Day 001: Recursion Basics

Using Abdul Bari’s, Mastering Data Structures & Algorithms using C and C++ to grok the basics. Now that I grok programming, understanding DSA should help me write and think better. And writing rough notes or thoughts to myself here, keeps me accountable and on track.1 Today’s topic? The Basics of Recursion Types of Recursion Tail Recursion Head Recursion Tree Recursion Indirect Recursion Nested Recursion Tail Recursion When a recursive call, is the last statement in a recursive function, that’s tail recursion func(n) { if (n>0) { blah … ; blah … ; blah … ; func(n-1); } } All the operations in the examples above happen at call time. Not when the function returns Tail Recursion vs Loops Tail recursion function can be written as a loop and vice versa Time taken by both, O(n) But the space taken by a loop is O(1) while a tail recursive function is O(n). The loop takes less space. Some compilers also do this under the hood (convert a tail recursive function into a loop) Head Recursion func(n) { if (n>0) { func(n-1); blah … ; blah … ; blah … ; } } In the example above, the recursion happens before anything else takes place. the recursion call is the first statement the rest of the function is processed, in the return process. (i.e. once the recursion call is done executing) Head Recursion vs Loops Head recursion function and a loop that gives a corresponding output are not quiet convertible from one to the other. Some work required. Tree Recursion func(n) { if (n>0) { blah … ; func(n-1); blah … ; func(n-1); blah … ; } } If a function calls itself multiple times, then we have ourselves a tree recursion Time complexity? pretty complex. A simple thing like the one above would be O(2n), while the space complexity is O(n) Indirect Recursion void A (int n) { if (something-something) { blah … ; B(n-1); } } void B (int n) { if (something-something) { blah … ; a(n-1); } } Two (or more) functions calling each other in a circular fashion. A -> B -> C -> A Nested Recursion void fun(int n) { if (blah-something) { blah fun(fun(n-1)) } } A recursive function passes a recursive call to itself as a parameter to the function. P.S. Subscribe to my mailing list! Forward these posts and letters to your friends and get them to subscribe! P.P.S. Feed my insatiable reading habit. ...

August 8, 2022 · Mario Jason Braganza

Focus on How Long You Read, Not How Much

Alternate Subtitle: The Best Advice I Could Give You About Reading Lots of Books. via a Tom Gauld Book1 Ever so often, after one of my reading updates on social media, some of my young friends ask me how I get so much reading done. ...

August 7, 2022 · Mario Jason Braganza

Tomorrow is Another Date

Org mode is slowly spreading its tentacles increasingly becoming something, I cannot live without, to manage my day. And I’m getting pretty consistent with it too! Like you see above, I use dates as my headlines, below which I list the various tasks for the day.1 And that’s where I run into my current itch to scratch. ...

July 31, 2022 · Mario Jason Braganza

Emacsclient Does Not Recognise Compose Key Sequences

Originally published 2021/10/27. Updated to include the .xssessionsrc point I run pretty often into this issue, so this is a checklist for me. Issue being, that I cannot use Compose key sequences to type out the characters I need. Case in point being, the apostrophe ’ and the quote marks “” , ‘’ that I use, all the live long day. Make sure that emacs is running as a service. It runs in your user, so check status with systemctl --user status emacs.service Do the normal computer user thing. Restart the service.systemctl --user restart emacs.service.1 Make sure the system is UTF-8 everywhere. (en_IN.UTF-8 does not work for me. Make sure it’s en_US.UTF-8) One place that Emacs looks is the .xsessionrc file in the home folder. These are the contents of mine. My Emacs refuses to let the compose key sequences work, unless it’s present LC_NUMERIC=en_US.UTF-8 LC_MONETARY=en_US.UTF-8 LC_PAPER=en_US.UTF-8 LC_NAME=en_US.UTF-8 LC_ADDRESS=en_US.UTF-8 LC_TELEPHONE=en_US.UTF-8 LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=en_US.UTF-8 LC_TIME=en_US.UTF-8 PAPERSIZE=a4 LANGUAGE=en_US LANG=en_US.UTF-8 if [ $DISPLAY != ":0" ] then export XAUTHORITY=${HOME}/.Xauthority fi This should do the trick 99% of the time. ...

July 31, 2022 · Mario Jason Braganza

FOSS.training / DGPLUG Summer Training 2022 Begins

Let’s get the important bits out of the way first. I have been both, busy and lazy. Mea culpa. But the new FOSS.training’s aka DGPLUG Summer Training cohort begins tomorrow, the 25th of July, 2022 (6.30pm IST). Come, join! Join the mailing list, here. Come join the #dgplug irc channel on Libera, because that’s where the training will be conducted. So, what is it? The summer training is short-ish, couple of months-ish long, series of meetups on irc.1 Mentors come. Students gather. A cohort forms. And we learn all about the free and open source world. If you’re a young person, looking to learn the culture and the tacit knowledge of how the free and open source or someone older or if you feel like someone who is on the outside looking in, all are welcome. ...

July 24, 2022 · Mario Jason Braganza

Setting Canonical URLs in Hugo

I steal quite a bit from other folk, to put on my blog.1 Case in point, is my last post where I stole the image from Tom Gauld. Or a few Seth Godin posts, somewhere on the blog, that I have posted in their entirety. While I do credit them in the post, I wished there was a way, I could programmatically tell the search engines and the bots of the world that I did in fact, steal from someplace and that they should actually be looking over there and leading people there. A little bit of searching, reavealed that there is in fact, such a way to do it. It’s called the Canonical URL. In a nutshell, it tells the machines to guide folk there, because that is the source of truth. ...

July 17, 2022 · Mario Jason Braganza