Recursion and Backtracking

Recursion:

Process of solving a problem by reducing it to a smaller versions of itself

Code

Dry run

// Factorial
Fac(int n)
{
		if(n < 2) 
			return n;
		return n * Fac(n - 1);
}

Code

Dry Run

// Find the largest num in a array / vector
int largenum(vector<int> &arr, int ind, int max)
{
    if (ind == arr.size())
    {
        return max;
    }
    if (arr[ind] > max)    
		{
        return largenum(arr, ind + 1, arr[ind]);
    }
    else
    {
        return largenum(arr, ind + 1, num);
    }
}

Code

Dry Run

//Fabonacci
int Fab(int n )
{
    if(n < 2)
    {
        return n;
    }
    return Fab(n - 1) + Fab(n - 2);
}

Tower of Hanoi

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);
}