Chapter 2: Recursion and Backtracking – 1. Recursion

Preface

In this chapter, we will look at one of the important topics Recursion, which will be used in most chapters, and its relative “Backtracking”.

2.1 What is Recursion?

Any function that calls itself is called recursive.
A recursive method solves a problem by calling a copy of itself to solve a smaller problem. This is called a recursive step.
The recursive step can lead to many such recursive calls.
The key is to make sure that the recursion ends.
Each time the function calls itself with a slightly simpler version of the original problem.
The sequence of smaller problems must eventually converge to the base case.

2.2 Why Recursion?

Recursion is a useful technique borrowed from mathematics.
Recursive code is usually shorter and easier to write than iterative code (for loop, while,..). In general, loops are turned into recursive functions when they are compiled or interpreted.
Recursion is most useful for tasks that can be defined in terms of similar subtasks.
For example, sorting, searching, and traversing problems often have simple recursive solutions.

2.3 Form of a recursive function

A recursive function performs a partial task by calling itself to perform subtasks.
At some point, the function encounters a subtask that it can perform without calling itself. This case, where the function does not repeat, is called the base case .
The case where a function calls itself to perform a subtask is called a recursive case.
We can write all recursive functions using the following format:

Example: The function calculates the factorial of a number n.

n ! n!$n!$ is the product of all integers from n to 1.
The definition of a recursive factorial looks like this:

n ! = first n! = 1$n!=1$

$n$ $=$ $0$ $n\; =\; 0$$n=0$

$n$ $!$ $=$ $n$ $($ $n$ $-$ $first$ $)$ $!$ $n!\; =\; n*(n-1)!$n ! = n _ ( n − 1 )! if

$n$$>$$0$ $n\; >\; 0$n > 0
This definition can easily be converted to a recursive implementation.
Here, the problem is to determine the value of

$n$ $!$ $n\; !$n ! , and the subproblem is to determine the value of

$($$n$$-$$first$ $)$ $!$ $(n\; –\; 1)\; !$( n − 1 )! .
In the recursive case, when n is greater than 1, the function calls itself to determine the value of

$($$n$$-$$first$ $)$ $!$ $(n\; –\; 1)\; !$( n − 1 )! and multiply it by n.
In the base case, when n is 0 or 1, the function only returns 1. The code should look like this:

2.4 Recursion and Memory (Visualization)

Each recursive call creates a new copy of that method (actually just variables) in memory.
When a method terminates (i.e. returns some data), the copy of that returning method is removed from memory.
Recursive solutions look simple, but visualization and tracing takes time.
To understand better, let’s consider the following example:

For this example, if we call the print function with n = 4, our memory assignments might visually look like this:

Now, let’s consider the factorial function above. The visualization of the factorial function with n = 4 would look like this:

2.5 Recursion Vs Loop

While discussing recursion, the basic question that comes to mind is: which way is better? – Loop or recursion?
The answer to this question depends on what we are trying to do .

The recursive approach reflects the problem we are trying to solve.
The recursive approach makes it simpler to solve a problem that may not have a clear answer. (Divide the subproblem into smaller problems).
However, recursion adds cost per recursive call (cost of space on stack memory).

2.6 A few notes about recursion

• Recursive algorithms have two types of cases, recursive cases and base cases.
• Every recursive function case must end at a base case.
• In general, loop solutions are more efficient than recursive solutions [due to function call overhead].
• A recursive algorithm can be implemented without calling a recursive function using stack, but it’s often more trouble than it’s worth. That means that any problem that can be solved recursively can also be solved iteratively.
• For some problems, there is no clear iterative algorithm.
• Some problems are best suited for recursive solutions while others are not.

2.7 Examples of algorithms using recursion

• Fibonacci Series, Factorial Finding
• Merge Sort, Quick Sort
• Binary Search
• Tree Traversals and many Tree Problems: InOrder, PreOrder PostOrder
• Graph Traversals: DFS [Depth First Search] and BFS [Breadth First Search]
• Dynamic Programming Examples
• Divide and Conquer Algorithms
• Towers of Hanoi
• Backtracking Algorithms (We will discuss in the next article)

In this chapter, we will cover some of the problems with recursion and the rest will be discussed in other chapters. By the time you’ve finished reading the entire series, you’ll have plenty of recursion problems.

Problem-1

Tower of Hanoi problem.
Tower of Hanoi is a math puzzle.
It consists of three vertical bars (or pins or towers) and several different sized discs that can slide onto any rod.
The puzzle begins with the disks on a stick in ascending order of size, the smallest at the top, thus forming a cone.

The goal of the puzzle is to move the entire stack to another bar, satisfying the following rules:

• Only one disk can be moved at a time.
• Each move consists of taking the upper disc from one of the bars and placing it on another stick, on top of the other discs that may already be on that stick.
• No disc can be placed on a smaller disk.

Solution :
Algorithm

• Move n – 1 top disk from Source to Sub-tower
• Move nth disk from Source to Destination tower
• Move n – 1 discs from the Side tower to the Destination tower.
• Moving the top n-1 disks from Source to Sub-Tower can again be considered a new problem and can be solved in a similar way. Once we solve Towers of Hanoi with three disks, we can solve it with any number of disks using the above algorithm.

Problem-2

Given an array, check if the array is sorted using recursion.
Solution :

Time Complexity:

O(n)O(n)O(n).

Space Complexity:

O(n)O(n)O(n)