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