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

Today’s topic?

The Basics of Recursion

• Types of Recursion
  1. Tail Recursion
  2. Head Recursion
  3. Tree Recursion
  4. Indirect Recursion
  5. 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(2ⁿ), 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.