Recursion.md

Recursion

Useful videos

• Recursion in Programming - Full Course
• Recursion Abdul Bari
• Dr Mostafa Saad -competitive programming pov
• Tower of Hanoi problem
• Short fun video video | fireship
• Recursion playlist | Mr.algorithms (arabic)
• Recurion intro | william Fiset
• How to think Recursivally
• 5 Simple Steps for Solving Any Recursive Problem
• advanced (needed for DFS in trees)

Useful articles

• GeeksForGeeks Tower of Hanoi
• A Common Mistake: Head Recursion

For practice

• codeforces Assiout sheet - Recursion
• LeetCode 45 recursion problems
• visualizing recursion
• Backtracking leetcode problems | neetcode

Formal definitions

• Recursive call : A method call in which the method being called is the same as the one making the call.
• Direct recursion : Recursion in which a method directly calls itself.
• Indirect recursion : Recursion in which a chain of two or more method calls returns to the method that originated the chain.
• Tail recursion : The case in which a function contains only a single recursive call and it is the last statement to be executed in the function.

Why and why not?

general format

if (SomeKnownCondition)       //base case
   SolutionStatement;
else
   RecursiveFunctionCall;    //general case

Note: If there're multiple recursion calls there might be multiple base casees

---

Tower of Hanoi problem

Solution pattern using recursion:

• Shift ‘N-1’ disks from ‘A’ to ‘B’, using C.
• Shift last disk from ‘A’ to ‘C’.
• Shift ‘N-1’ disks from ‘B’ to ‘C’, using A.

Code implementation:

// C++ recursive function to 
// solve tower of hanoi puzzle 
#include <bits/stdc++.h> 
using namespace std; 

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) 
{ 
	if (n == 0) { 
		return; 
	} 
	towerOfHanoi(n - 1, from_rod, aux_rod, to_rod); 
	cout << "Move disk " << n << " from rod " << from_rod << " to rod " << to_rod << endl; 
	towerOfHanoi(n - 1, aux_rod, to_rod, from_rod); 
} 

// Driver code 
int main() 
{ 
	int N = 3; 

	// A, B and C are names of rods
   towerOfHanoi(N, 'A', 'C', 'B'); 
	return 0; 
} 

// This is code is contributed by rathbhupendra 

Time complexity: O(2^N), There are two possibilities for every disk. Therefore, 2 * 2 * 2 * . . . * 2(N times) is 2^N

---

Tail recursion vs Head recursion

Tail recursion	Head recursion
Recursive call is typically last statement and no operations are performed after it	Recursive call isn't the last thing to excute, there are additional operations performed after it
Operations are performed at calling time	Operations are performed at return time
Can be easily converted to a loop	Not easily converted to a loop
Better memory efficiency especially in languages with tail call optimization.	Consume more memory due to multiple call frames being stored on the stack.

Tail recurion example:

void print(int x)
{
	if(x == 0)
		return;
	std::cout << x;
	print(x-1);
}

Head recursion example:

void print(int x)
{
	if(x == 0)
		return;
	print(x-1);
	std::cout << x;
}

Another example:

int factorial(int n)
{
	if(n == 1)
        	return 1;
    	return n * factorial(n - 1);
}

Warning

Don't get tricked here! this is a head recursion not tail recursion, the recursive call factorial(n - 1) is made before the multiplication operation

---