Recursion and Backtracking
Introduction to Recursion
Any function which calls itself is called recursion. A recursive method solves a problem by calling a copy of itself to work on a smaller problem. Each time a function calls itself with a slightly simpler version of the original problem. This sequence of smaller problems must eventually converge on a base case.
Working of recursion
We can define the steps of the recursive approach by summarizing the above three steps:
- Base case: A recursive function must have a terminating condition at which the process will stop calling itself. Such a case is known as the base case. In the absence of a base case, it will keep calling itself and get stuck in an infinite loop. Soon, the recursion depth* will be exceeded and it will throw an error.
- Recursive call (Smaller problem): The recursive function will invoke itself on a smaller version of the main problem. We need to be careful while writing this step as it is crucial to correctly figure out what your smaller problem is.
- Small calculation (Self-work ): Generally, we perform a calculation step in each recursive call. We can achieve this calculation step before or after the recursive call depending upon the nature of the problem.
Note*: Recursion uses an in-built stack that stores recursive calls. Hence, the number of recursive calls must be as small as possible to avoid memory-overflow. If the number of recursion calls exceeded the maximum permissible amount, the recursion depth* will be exceeded. This condition is called stack overflow.
Now, let us see how to solve a few common problems using Recursion.
Problem Statement - Find Factorial of a number n.
Factorial of any number n is defined as n! = n * (n-1) * (n-2) * … *1. Ex: 5! = 5 * 4 * 3 * 2 * 1 = 120;
Let n = 5 ;
In recursion, the idea is that we represent a problem in terms of smaller problems. We know that 5! = 5 * 4!. Let’s assume that recursion will give us an answer of 4!. Now to get the solution to our problem will become 4 * (the answer of the recursive call).
Similarly, when we give a recursive call for 4!; recursion will give us an answer of 3!. Since the same work is done in all these steps we write only one function and give it a call recursively. Now, what if there is no base case? Let's say 1! Will give a call to 0!; 0! will give a call to -1! (doesn’t exist) and so on. Soon the function call stack will be full of method calls and give an error Stack Overflow. To avoid this we need a base case. So in the base case, we put our own solution to one of the smaller problems.
function factorial(n)
// base case
if n equals 0
return 1
// getting answer of the smaller problem
recursionResult = factorial(n-1)
// self work
ans = n * recursionResult
return ans
Problem Statement - Find nth fibonacci.
Let n = 4
Depending upon the question, the bigger problem can depend on N number of smaller problems.
function fibonacci(n)
// base case
if n equals 1 OR 0
return n
// getting answer of the smaller problem
recursionResult1 = fibonacci(n - 1)
recursionResult2 = fibonacci(n - 2)
// self work
ans = recursionResult1 + recursionResult2
return ans
Problem Statement - Check if an array is sorted
For example:
- If the array is {2, 4, 8, 9, 9, 15}, then the output should be true.
- If the array is {5, 8, 2, 9, 3}, then the output should be false.
function isArraySorted(arr, idx) // 0 is passed in idx
// base case
if idx equals arr.length - 1
return true
// getting answer of the smaller problem
recursionResult = isArraySorted(arr, idx+1)
// self work
ans = recursionResult & arr[idx] <= arr[idx+1]
return ans
Binary Search with Recursion
Binary Search: Search in a sorted array by repeatedly dividing the array into half and searching in only one half.
You are given a target element X and a sorted array. You need to check if X is present in the array. Consider the algorithm given below:
- Compare X with the middle element in the array.
- If X is the same as the middle element, we return the index of the middle element.
- Else if X is greater than the mid element, then X can only lie in the right (greater) half subarray after the mid element. Thus, we apply the algorithm, recursively, for the right half.
- Else if X is smaller, the target X must lie in the left (lower) half. So we apply the algorithm, recursively, for the left half.
/*
array from leftidx(0) to rightidx(arr.length-1) is considered
*/
function binarySearch(arr, leftidx , rightidx , target)
// base case : element not found
if leftidx > rightidx
return -1
middle = (leftidx + rightidx) / 2
if arr[middle] equals target
return middle
else if arr[middle] > target
return binarySearch(arr , leftidx , middle - 1 , target)
else
return binarySearch(arr, middle + 1, rightidx, target) Divide and Conquer
Divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
Sorting Techniques Using Recursion/Divide and Conquer - Merge Sort
Merge sort requires dividing a given list into equal halves until it can no longer be divided. By definition, if it is only one element in the list, it is sorted. Then, merge sort combines/merges the smaller sorted lists keeping the new list sorted too.
- If it is only one element in the list it is already sorted, return.
- Divide the list recursively into two halves until it can’t be divided further.
- Merge the smaller lists into a new list in sorted order.
It has just one disadvantage and that is it’s not an in-place sorting technique i.e. it creates a copy of the array and then works on that copy.
/*
array from leftidx(0) to rightidx(arr.length-1) is considered
*/
function mergeSort(arr, leftidx , rightidx )
// base case : only 1 element to be sorted
if leftidx == rightidx
return
middle = (leftidx + rightidx) / 2
// smaller problems
mergerSort(arr, leftidx, middle)
mergeSort(arr, middle + 1, rightidx)
// selfwork
merge(leftidx , middle, rightidx)
function merge(arr, leftidx , middle , rightidx)
leftlo = leftidx
rightlo = middle+1
idx = 0
// create an array temp of size (rightidx - leftidx + 1)
while leftlo <= middle AND rightlo <= rightidx
if arr[leftlo] < arr[rightlo]
temp[idx] = arr[leftlo]
leftlo++
idx++
else
temp[idx] = arr[rightlo]
rightlo++
idx++
while leftlo <= middle
temp[idx] = arr[leftlo]
leftlo++
idx++
while rightlo <= rightidx
temp[idx] = arr[rightlo]
rightlo++
idx++
//copy temp to original array
count = 0
while count < temp.length AND leftidx <= rightidx
arr[leftidx] = temp[count]
leftidx++
count++
The following diagram shows the complete merge sort process for an example array [38,27,43,3,9,82,10]. If we take a closer look at the diagram, we can see that the array is recursively divided into two halves till the size becomes 1. Once the size becomes 1, the merge processes come into action and start merging arrays back till the complete array is merged.
Sorting Techniques Using Recursion/Divide and Conquer - QuickSort
Based on the Divide-and-Conquer approach, the quicksort algorithm can be explained as:
- Divide: The array is divided into subparts taking pivot as the partitioning point. The elements smaller than the pivot are placed to the left of the pivot and the elements greater than the pivot are placed to the right side.
- Conquer: The left and right sub-parts are again partitioned using the by selecting pivot elements for them. This can be achieved by recursively passing the subparts into the algorithm.
- Combine: This part does not play a significant role in quicksort. The array is already sorted at the end of the conquer step.
The advantage of quicksort over merge sort is that it does not require any extra space to sort the given array, that it is an in-place sorting technique.
There are many ways to pick a pivot element:
- Always pick the first element as the pivot.
- Always pick the last element as the pivot.
- Pick a random element as the pivot.
- Pick the middle element as the pivot.
The following diagram shows the complete quick sort process, by considering the first element as the pivot element, for an example array [8,1,5,14,4,15,12,6,2,11,10,7,9].
- In step 1, 8 is taken as the pivot.
- In step 2, 6 and 12 are taken as pivots.
- In step 3, 4 and 10 are taken as pivots.
- We keep dividing the list about pivots till there are only 2 elements left in a sublist.
/*
array from lo(0) to hi(arr.length-1) is considered
*/
function quickSort(arr, lo , hi )
if (lo >= hi)
return
pivot = arr[lo]
// partitioning
left = lo
right = hi
while left <= right
//move left to a problem
while arr[left] < pivot
left++
//move right to a problem
while arr[right] > pivot
right--
//problem solve : swap
if left <= right
temp = arr[left]
arr[left] = arr[right]
arr[right] = temp
left++
right--
// smaller problems
quickSort(arr, lo, right)
quickSort(arr, left, hi)
Introduction to Backtracking
Backtracking is a famous algorithmic-technique for solving/resolving problems recursively by trying to build a solution incrementally. Solving one piece at a time, and removing those solutions that fail to satisfy the constraints of the problem at any point of time (by time, here, is referred to as the time elapsed till reaching any level of the search tree) is the process of backtracking.
In other words, Backtracking can be termed as a general algorithmic technique that considers searching every possible combination in order to solve a computational problem.
There are generally three types of problems in backtracking -
- Decision Problems: In these types of problems, we search for any feasible solution.
- Optimization Problems: In these types of problems, we search for the best possible solution.
- Enumerations Problems: In these types of problems, we find all feasible solutions.
Backtracking and recursion
Backtracking is based on recursion, where the algorithm makes an effort to build a solution to a computational problem incrementally. Whenever the algorithm needs to choose between multiple possible alternatives, it simply tries all possible options for the solution recursively step-by-step. The usual scenario is that you are faced with a number of options, and you must choose one of these. After you make your choice you will get a new set of options; just what set of options you get depends on what choice you made. This procedure is repeated over and over until you reach a final state. If you made a good sequence of choices, your final state is a goal state; if you didn't, it isn't.
In recursion, the function calls itself until it reaches a base case. In backtracking, we use recursion in order to explore all the possibilities until we get the desired solution for the problem. Backtracking works right after the recursive step, i.e if the recursive step results in a solution that is not desired, it retraces back and looks for other possible options.
Rat Maze problem
Given a 2D-grid, for simplicity let us assume that the grid is a square matrix of size N, having some cells as free and some as blocked. Given source S and destination D, we need to find whether there exists a path from source to destination in the maze, by traversing through free cells only.
Let us assume that source S is at the top-left corner of the maze and destination D is at the bottom-right corner of the maze, and the movements allowed are to either move to the right or to down.
The black-colored cells represent the blocked cells and white-colored cells represent the free cells. The possible path from source to destination is -
NOTE: There may be multiple possible paths from source to destination.
We will use backtracking to find whether there exists a path from source to destination in the given maze.
Steps:
- If the destination point i.e N is reached, return true.
- Else
- Check if the current position is a valid position i.e the position is within the bounds of the maze as well as it is a free position.
- Mark the current position as 1, denoting that the position can lead to a possible solution.
- Move forward, and recursively check if this move leads to reach to the destination.
- If the above move fails to reach the destination, then move downward, and recursively check if this move leads to reach the destination.
- If none of the above moves leads to the destination, then mark the current position as 0, denoting that it is not possible to reach the destination from this position.
Pseudocode:
function isValid(x, y, N)
/*
Check if the position is within the bounds of the maze
and the position does not contain a blocked cell.
*/
if(x <= N and y <= N and x, y is not blocked)
return true
else
return false
function RatMaze(maze[][], x, y, N)
/*
x, y is the current position of the rat in the maze.
Check if the current position is a valid position.
*/
if isValid(x, y, N)
mark[x][y] = 1
else
return false
/*
If the current position is the bottom-right corner, i.e N,
then we have found a solution
*/
if x equals N and y equals N
mark[x][y] = 1
return true
/*
Otherwise, try moving forward or downward to look for
other possible solutions.
*/
bool found = RatMaze(maze,x+1,y,N) OR RatMaze(maze,x,y+1,N)
/*
If a solution is found from the current position by moving
forward or downward, then return true, otherwise mark the
current position as 0, as it is not possible to reach the end
of the maze.
*/
if(found)
return true
else
mark[x][y] = 0
return false
N-Queens Problem
Given an NxN chessboard, we need to arrange N queens on the board in such a way that no two queens attack each other. A queen can attack horizontally, vertically, or diagonally.
Below is a diagram showing how 4 queens can be placed on the chessboard of size 4x4, such that no two queens attack each other.
In the above diagram, the 4 queens are represented by Q1, Q2, Q3, Q4 and it shows the possible valid arrangements of the 4 queens on the chessboard.
NOTE: There can be multiple valid arrangements for the queens on the chessboard.
We will use backtracking to find a valid arrangement of the queens on the given chessboard. We place the first queen arbitrarily anywhere within the board, and then place the next queen in a position that is not attacked by any other queens placed so far, if no such position is present we backtrack and change the position of the previous queens. A solution is found if we are able to place all the queens on the chessboard.
Steps:
- Place a queen arbitrarily at any position on the chessboard.
- Check if this position is safe, i.e it is not attacked by any other queens.
- If the position is not safe, then look for other positions on the board, and if no such position is found, then return false as we cannot place any more queens.
- If the position is safe, then recursively check for Q-1 queens, if the function returns true, in other words, all queens were placed successfully on the board, then return true.NOTE: Q denoting the number of queens to be placed, N is passed as the value in the function call, representing the value of Q initially, as we need to place N queens on the board.
Pseudocode:
function isValid(x,y,board[][],N)
/*
Check if the position at x,y is not attacked by any other
queen.
Check if no position is marked 1 in the same row.
Check if no position is marked 1 in the same column.
Check if no position is marked 1 in the diagonals.
*/
for i = 0 to N - 1
if board[x][i] equals 1 or board[i][y] equals 1
return false
tempx = x
tempy = y
while tempx >= 0 and tempy < N
if board[tempx][tempy] equals 1
return false
tempx -= 1
tempy += 1
tempx = x
tempy = y
while tempx < N and tempy >= 0
if board[tempx][tempy] equals 1
return false
tempx += 1
tempy -= 1
tempx = x
tempy = y
while tempx >= 0 and tempy >= 0
if board[tempx][tempy] equals 1
return false
tempx -= 1
tempy -= 1
tempx = x
tempy = y
while tempx < N and tempy < N
if board[tempx][tempy] equals 1
return false
tempx += 1
tempy += 1
// The position is a safe position, return true
return true
function N-Queens(Q, board[][], N)
// Q represents the number of queens to be placed on the board.
// Base Case, when all queens have been placed
if Q equals 0
return true
/*
For each possible position on the board,
check if the position is safe i.e it is
not attacked by any other queen placed so far.
*/
for i = 0 to N - 1
for j = 0 to N - 1
bool can = isValid(i, j, board, N)
/*
If the position is safe, then mark the position
on the board as 1,and check recursively for Q-1
queens if they can be placed successfully.
*/
if isValid is true
board[i][j] = 1
bool solve = N - Queens(Q - 1,board,N)
/*
The remaining queens can be placed successfully,
return true, otherwise, unmark the position
on the board,and check for other possible
options.
*/
if solve is true
return true
else if
board[i][j] = 0
else
continue
/*
Since there was no possible option to place
a queen on the board,so return false.
*/
return false
Applications of backtracking
- Backtracking is useful in solving puzzles such as the Eight queen puzzle, Crosswords, Verbal arithmetic, Sudoku, and Peg Solitaire.
- The technique is also useful in solving combinatorial optimization problems such as parsing and the knapsack.
- The backtracking search algorithm is used in load frequency control of multi-area interconnected power systems.
Advantages of backtracking
- It is a step-by-step representation of a solution to a given problem, which is very easy to understand.
- It is easy to first develop an algorithm, and then convert it into a flowchart and into a computer program.
- It is very easy to implement and contains fewer lines of code, almost all of them being generally few lines of recursive function code.
Disadvantages of backtracking
- More optimal algorithms for the given problem may exist.
- Very time inefficient in a lot of cases when the branching factor is large.
- Can lead to large space complexities because of the recursive function call stack.