Data Structure - Recursion Basics

Some computer programming languages allow a module or function to call itself. This technique is known as recursion. In recursion, a function α either calls itself directly or calls a function β that in turn calls the original function α. The function α is called recursive function.

Example − a function calling itself.

int function(int value) { if(value < 1) return; function(value - 1);

printf("%d ",value);
} Example − a function that calls another function which in turn calls it again.

int function1(int value1) { if(value1 < 1) return; function2(value1 - 1); printf("%d ",value1);
} int function2(int value2) { function1(value2); } Properties A recursive function can go infinite like a loop. To avoid infinite running of recursive function, there are two properties that a recursive function must have −

Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively.

Progressive approach − The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.

Implementation Many programming languages implement recursion by means of stacks. Generally, whenever a function (caller) calls another function (callee) or itself as callee, the caller function transfers execution control to the callee. This transfer process may also involve some data to be passed from the caller to the callee.

This implies, the caller function has to suspend its execution temporarily and resume later when the execution control returns from the callee function. Here, the caller function needs to start exactly from the point of execution where it puts itself on hold. It also needs the exact same data values it was working on. For this purpose, an activation record (or stack frame) is created for the caller function.

Activation Records This activation record keeps the information about local variables, formal parameters, return address and all information passed to the caller function.

Analysis of Recursion One may argue why to use recursion, as the same task can be done with iteration. The first reason is, recursion makes a program more readable and because of latest enhanced CPU systems, recursion is more efficient than iterations.

Time Complexity In case of iterations, we take number of iterations to count the time complexity. Likewise, in case of recursion, assuming everything is constant, we try to figure out the number of times a recursive call is being made. A call made to a function is Ο(1), hence the (n) number of times a recursive call is made makes the recursive function Ο(n).

Space Complexity Space complexity is counted as what amount of extra space is required for a module to execute. In case of iterations, the compiler hardly requires any extra space. The compiler keeps updating the values of variables used in the iterations. But in case of recursion, the system needs to store activation record each time a recursive call is made. Hence, it is considered that space complexity of recursive function may go higher than that of a function with iteration.

Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings is as depicted −

Tower Of Hanoi These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger one. There are other variations of the puzzle where the number of disks increase, but the tower count remains the same.

Rules The mission is to move all the disks to some another tower without violating the sequence of arrangement. A few rules to be followed for Tower of Hanoi are −

Only one disk can be moved among the towers at any given time. Only the "top" disk can be removed. No large disk can sit over a small disk. Following is an animated representation of solving a Tower of Hanoi puzzle with three disks.

Tower Of Hanoi Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.

Algorithm To write an algorithm for Tower of Hanoi, first we need to learn how to solve this problem with lesser amount of disks, say → 1 or 2. We mark three towers with name, source, destination and aux (only to help moving the disks). If we have only one disk, then it can easily be moved from source to destination peg.

If we have 2 disks −

First, we move the smaller (top) disk to aux peg. Then, we move the larger (bottom) disk to destination peg. And finally, we move the smaller disk from aux to destination peg. Tower Of Hanoi with Two Disks So now, we are in a position to design an algorithm for Tower of Hanoi with more than two disks. We divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all other (n-1) disks are in the second part.

Our ultimate aim is to move disk n from source to destination and then put all other (n1) disks onto it. We can imagine to apply the same in a recursive way for all given set of disks.

The steps to follow are −

Step 1 − Move n-1 disks from source to aux Step 2 − Move nth disk from source to dest Step 3 − Move n-1 disks from aux to dest A recursive algorithm for Tower of Hanoi can be driven as follows −

START Procedure Hanoi(disk, source, dest, aux)

IF disk == 1, THEN move disk from source to dest
ELSE Hanoi(disk - 1, source, aux, dest) // Step 1 move disk from source to dest // Step 2 Hanoi(disk - 1, aux, dest, source) // Step 3 END IF

END Procedure STOP

          Data Structure - Recursion Basics

Some computer programming languages allow a module or function to call itself. This technique is known as recursion. In recursion, a function α either calls itself directly or calls a function β that in turn calls the original function α. The function α is called recursive function.

Example − a function calling itself.

int function(int value) { if(value < 1) return; function(value - 1);

printf("%d ",value);
} Example − a function that calls another function which in turn calls it again.

int function1(int value1) { if(value1 < 1) return; function2(value1 - 1); printf("%d ",value1);
} int function2(int value2) { function1(value2); } Properties A recursive function can go infinite like a loop. To avoid infinite running of recursive function, there are two properties that a recursive function must have −

Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively.

Progressive approach − The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.

Implementation Many programming languages implement recursion by means of stacks. Generally, whenever a function (caller) calls another function (callee) or itself as callee, the caller function transfers execution control to the callee. This transfer process may also involve some data to be passed from the caller to the callee.

This implies, the caller function has to suspend its execution temporarily and resume later when the execution control returns from the callee function. Here, the caller function needs to start exactly from the point of execution where it puts itself on hold. It also needs the exact same data values it was working on. For this purpose, an activation record (or stack frame) is created for the caller function.

Activation Records This activation record keeps the information about local variables, formal parameters, return address and all information passed to the caller function.

Analysis of Recursion One may argue why to use recursion, as the same task can be done with iteration. The first reason is, recursion makes a program more readable and because of latest enhanced CPU systems, recursion is more efficient than iterations.

Time Complexity In case of iterations, we take number of iterations to count the time complexity. Likewise, in case of recursion, assuming everything is constant, we try to figure out the number of times a recursive call is being made. A call made to a function is Ο(1), hence the (n) number of times a recursive call is made makes the recursive function Ο(n).

Space Complexity Space complexity is counted as what amount of extra space is required for a module to execute. In case of iterations, the compiler hardly requires any extra space. The compiler keeps updating the values of variables used in the iterations. But in case of recursion, the system needs to store activation record each time a recursive call is made. Hence, it is considered that space complexity of recursive function may go higher than that of a function with iteration.

Tower of Hanoi, is a mathematical puzzle which consists of three towers (pegs) and more than one rings is as depicted −

Tower Of Hanoi These rings are of different sizes and stacked upon in an ascending order, i.e. the smaller one sits over the larger one. There are other variations of the puzzle where the number of disks increase, but the tower count remains the same.

Rules The mission is to move all the disks to some another tower without violating the sequence of arrangement. A few rules to be followed for Tower of Hanoi are −

Only one disk can be moved among the towers at any given time. Only the "top" disk can be removed. No large disk can sit over a small disk. Following is an animated representation of solving a Tower of Hanoi puzzle with three disks.

Tower Of Hanoi Tower of Hanoi puzzle with n disks can be solved in minimum 2n−1 steps. This presentation shows that a puzzle with 3 disks has taken 23 - 1 = 7 steps.

Algorithm To write an algorithm for Tower of Hanoi, first we need to learn how to solve this problem with lesser amount of disks, say → 1 or 2. We mark three towers with name, source, destination and aux (only to help moving the disks). If we have only one disk, then it can easily be moved from source to destination peg.

If we have 2 disks −

First, we move the smaller (top) disk to aux peg. Then, we move the larger (bottom) disk to destination peg. And finally, we move the smaller disk from aux to destination peg. Tower Of Hanoi with Two Disks So now, we are in a position to design an algorithm for Tower of Hanoi with more than two disks. We divide the stack of disks in two parts. The largest disk (nth disk) is in one part and all other (n-1) disks are in the second part.

Our ultimate aim is to move disk n from source to destination and then put all other (n1) disks onto it. We can imagine to apply the same in a recursive way for all given set of disks.

The steps to follow are −

Step 1 − Move n-1 disks from source to aux Step 2 − Move nth disk from source to dest Step 3 − Move n-1 disks from aux to dest A recursive algorithm for Tower of Hanoi can be driven as follows −

START Procedure Hanoi(disk, source, dest, aux)

IF disk == 1, THEN move disk from source to dest
ELSE Hanoi(disk - 1, source, aux, dest) // Step 1 move disk from source to dest // Step 2 Hanoi(disk - 1, aux, dest, source) // Step 3 END IF

END Procedure STOP

A linked list is a sequence of data structures, which are connected together via links.

Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List.

Link − Each link of a linked list can store a data called an element.

Next − Each link of a linked list contains a link to the next link called Next.

Linkedlist − A Linked List contains the connection link to the first link called First.

Linked List Representation Linked list can be visualized as a chain of nodes, where every node points to the next node.

Linked List As per the above illustration, following are the important points to be considered.

Linked List contains a link element called first.

Each link carries a data field(s) and a link field called next.

Each link is linked with its next link using its next link.

Last link carries a link as null to mark the end of the list.

Types of Linked List Following are the various types of linked list.

Simple Linked List − Item navigation is forward only.

Doubly Linked List − Items can be navigated forward and backward.

Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.

Basic Operations Following are the basic operations supported by a list.

Insertion − Adds an element at the beginning of the list.

Deletion − Deletes an element at the beginning of the list.

Display − Displays the complete list.

Search − Searches an element using the given key.

Delete − Deletes an element using the given key.

Insertion Operation Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it has to be inserted.

Linked List Insertion Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point B.next to C −

NewNode.next −> RightNode; It should look like this −

Linked List Insertion Now, the next node at the left should point to the new node.

LeftNode.next −> NewNode; Linked List Insertion This will put the new node in the middle of the two. The new list should look like this −

Linked List Insertion Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL.

Deletion Operation Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate the target node to be removed, by using searching algorithms.

Linked List Deletion The left (previous) node of the target node now should point to the next node of the target node −

LeftNode.next −> TargetNode.next; Linked List Deletion This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at.

TargetNode.next −> NULL; Linked List Deletion We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate memory and wipe off the target node completely.

Linked List Deletion Reverse Operation This operation is a thorough one. We need to make the last node to be pointed by the head node and reverse the whole linked list.

Linked List Reverse Operation First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node −

Linked List Reverse Operation We have to make sure that the last node is not the last node. So we'll have some temp node, which looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their previous nodes one by one.

Linked List Reverse Operation Except the node (first node) pointed by the head node, all nodes should point to their predecessor, making them their new successor. The first node will point to NULL.

Linked List Reverse Operation We'll make the head node point to the new first node by using the temp node.

Doubly Linked List is a variation of Linked list in which navigation is possible in both ways, either forward and backward easily as compared to Single Linked List. Following are the important terms to understand the concept of doubly linked list.

Link − Each link of a linked list can store a data called an element.

Next − Each link of a linked list contains a link to the next link called Next.

Prev − Each link of a linked list contains a link to the previous link called Prev.

LinkedList − A Linked List contains the connection link to the first link called First and to the last link called Last.

Doubly Linked List Representation Doubly Linked List As per the above illustration, following are the important points to be considered.

Doubly Linked List contains a link element called first and last.

Each link carries a data field(s) and two link fields called next and prev.

Each link is linked with its next link using its next link.

Each link is linked with its previous link using its previous link.

The last link carries a link as null to mark the end of the list.

Basic Operations Following are the basic operations supported by a list.

Insertion − Adds an element at the beginning of the list.

Deletion − Deletes an element at the beginning of the list.

Insert Last − Adds an element at the end of the list.

Delete Last − Deletes an element from the end of the list.

Insert After − Adds an element after an item of the list.

Delete − Deletes an element from the list using the key.

Display forward − Displays the complete list in a forward manner.

Display backward − Displays the complete list in a backward manner.

Insertion Operation Following code demonstrates the insertion operation at the beginning of a doubly linked list.

Example //insert link at the first location void insertFirst(int key, int data) {

//create a link struct node link = (struct node) malloc(sizeof(struct node)); link->key = key; link->data = data;

if(isEmpty()) { //make it the last link last = link; } else { //update first prev link head->prev = link; }

//point it to old first link link->next = head;

//point first to new first link head = link; } Deletion Operation Following code demonstrates the deletion operation at the beginning of a doubly linked list.

Example //delete first item struct node* deleteFirst() {

//save reference to first link struct node *tempLink = head;

//if only one link if(head->next == NULL) { last = NULL; } else { head->next->prev = NULL; }

head = head->next;

//return the deleted link return tempLink; } Insertion at the End of an Operation Following code demonstrates the insertion operation at the last position of a doubly linked list.

Example //insert link at the last location void insertLast(int key, int data) {

//create a link struct node link = (struct node) malloc(sizeof(struct node)); link->key = key; link->data = data;

if(isEmpty()) { //make it the last link last = link; } else { //make link a new last link last->next = link;

  //mark old last node as prev of new link
  link->prev = last;

}

//point last to new last node last = link; }

Originally posted by @Manish4Kumar in https://github.com/subhamengine/DataStructures-and-Algorithm/issues/18#issuecomment-940689532

#4 In C++, string is an object of std::string class that represents sequence of characters. We can perform many operations on strings such as concatenation, comparison, conversion etc. C++ String Example Let's see the simple example of C++ string.

#include
using namespace std;
int main( ) {
string s1 = "Hello";
char ch[] = { 'C', '+', '+'};
string s2 = string(ch);
cout<<s1<<endl;
cout<<s2<<endl;
}
Output:

Hello C++

String Data Structure

Practice Problems on String Strings are defined as an array of characters. The difference between a character array and a string is the string is terminated with a special character ‘\0’.

Declaring a string is as simple as declaring a one dimensional array. Below is the basic syntax for declaring a string in C programming language. char str_name[size]; Problems:- #include
#include
using namespace std;
int main ()
{
char key[] = "mango";
char buffer[50];
do {
cout<<"What is my favourite fruit? ";
cin>>buffer;
} while (strcmp (key,buffer) != 0);
cout<<"Answer is correct!!"<<endl;
return 0;
}
Output:

What is my favourite fruit? apple What is my favourite fruit? banana What is my favourite fruit? mango Answer is correct!!

Count of distinct groups of strings formed after performing equivalent operation Medium

Given an array arr[] of N strings consisting of lowercase alphabets, the task is to find the number of distinct groups of strings formed after performing the equivalent operation. Two strings are said to be equivalent if there exists the same character in both the strings and if there exists another string that is equivalent to one of the strings in the group of equivalent string then that string is also equivalent to that group.

Examples;- Problems:- // C++ program for the above approach #include<bits/stdc++.h> using namespace std;

// Function to perform the find operation // to find the parent of a disjoint set int Find(vector& parent, int a) { return parent[a] = (parent[a] == a ? a : Find(parent, parent[a])); }

// Function to perform union operation // of disjoint set union void Union(vector& parent, vector& rank, int a, int b) {

// Find the parent of node a and b
a = Find(parent, a);
b = Find(parent, b);

// Update the rank
if (rank[a] == rank[b])
	rank[a]++;
if (rank[a] > rank[b])
	parent[b] = a;
else
	parent[a] = b;

}

// Function to find the number of distinct // strings after performing the // given operations void numOfDistinctStrings(string arr[], int N) { // Stores the parent elements // of the sets vector parent(27);

// Stores the rank of the sets
vector<int> rank(27, 0);

for (int j = 0; j < 27; j++) {
	// Update parent[i] to i
	parent[j] = j;
}

// Stores the total characters
// traversed through the strings
vector<bool> total(26, false);

// Stores the current characters
// traversed through a string
vector<bool> current(26, false);

for (int i = 0; i < N; i++) {

	for (int j = 0; j < 26; j++) {

		// Update current[i] to false
		current[j] = false;
	}

	for (char ch : arr[i]) {

		// Update current[ch - 'a'] to true
		current[ch - 'a'] = true;
	}

	for (int j = 0; j < 26; j++) {

		// Check if current[j] is true
		if (current[j]) {

			// Update total[j] to true
			total[j] = true;

			// Add arr[i][0] - 'a' and
			// j elements to same set
			Union(parent, rank,
				arr[i][0] - 'a', j);
		}
	}
}

// Stores the count of distinct strings
int distCount = 0;
for (int i = 0; i < 26; i++) {

	// Check total[i] is true and
	// parent of i is i only
	if (total[i] && Find(parent, i) == i) {

		// Increment the value of
		// distCount by 1
		distCount++;
	}
}

// Print the value of distCount
cout << distCount << endl;

}

// Driver Code int main() { string arr[] = { "a", "ab", "b", "d" }; int N = sizeof(arr) / sizeof(arr[0]); numOfDistinctStrings(arr, N);

return 0;

}

Output: 2

C++ String Concat Example

Let's see the simple example of string concatenation using strcat() function.

#include
#include
using namespace std;
int main()
{
char key[25], buffer[25];
cout << "Enter the key string: ";
cin.getline(key, 25);
cout << "Enter the buffer string: ";
cin.getline(buffer, 25);
strcat(key, buffer);
cout << "Key = " << key << endl;
cout << "Buffer = " << buffer<<endl;
return 0;
}
Output:

Enter the key string: Welcome to Enter the buffer string: C++ Programming. Key = Welcome to C++ Programming. Buffer = C++ Programming.

C++ String Copy Example Problems:- Let's see the simple example of copy the string using strcpy() function.

#include
#include
using namespace std;
int main()
{
char key[25], buffer[25];
cout << "Enter the key string: ";
cin.getline(key, 25);
strcpy(buffer, key);
cout << "Key = "<< key << endl;
cout << "Buffer = "<< buffer<<endl;
return 0;
}
Output:

Enter the key string: C++ Tutorial Key = C++ Tutorial Buffer = C++ Tutorial

C++ String Length Example Problems-

#include
#include
using namespace std;
int main()
{
char ary[] = "Welcome to C++ Programming";
cout << "Length of String = " << strlen(ary)<<endl;
return 0;
}

Output:

Length of String = 26

Originally posted by @Manish4Kumar in https://github.com/subhamengine/DataStructures-and-Algorithm/issues/12#issuecomment-939409966

#4 In C++, string is an object of std::string class that represents sequence of characters. We can perform many operations on strings such as concatenation, comparison, conversion etc. C++ String Example Let's see the simple example of C++ string.

#include
using namespace std;
int main( ) {
string s1 = "Hello";
char ch[] = { 'C', '+', '+'};
string s2 = string(ch);
cout<<s1<<endl;
cout<<s2<<endl;
}
Output:

Hello C++

String Data Structure

Practice Problems on String Strings are defined as an array of characters. The difference between a character array and a string is the string is terminated with a special character ‘\0’.

Declaring a string is as simple as declaring a one dimensional array. Below is the basic syntax for declaring a string in C programming language. char str_name[size]; Problems:- #include
#include
using namespace std;
int main ()
{
char key[] = "mango";
char buffer[50];
do {
cout<<"What is my favourite fruit? ";
cin>>buffer;
} while (strcmp (key,buffer) != 0);
cout<<"Answer is correct!!"<<endl;
return 0;
}
Output:

What is my favourite fruit? apple What is my favourite fruit? banana What is my favourite fruit? mango Answer is correct!!

Count of distinct groups of strings formed after performing equivalent operation Medium

Given an array arr[] of N strings consisting of lowercase alphabets, the task is to find the number of distinct groups of strings formed after performing the equivalent operation. Two strings are said to be equivalent if there exists the same character in both the strings and if there exists another string that is equivalent to one of the strings in the group of equivalent string then that string is also equivalent to that group.

Examples;- Problems:- // C++ program for the above approach #include<bits/stdc++.h> using namespace std;

// Function to perform the find operation // to find the parent of a disjoint set int Find(vector& parent, int a) { return parent[a] = (parent[a] == a ? a : Find(parent, parent[a])); }

// Function to perform union operation // of disjoint set union void Union(vector& parent, vector& rank, int a, int b) {

// Find the parent of node a and b
a = Find(parent, a);
b = Find(parent, b);

// Update the rank
if (rank[a] == rank[b])
	rank[a]++;
if (rank[a] > rank[b])
	parent[b] = a;
else
	parent[a] = b;

}

// Function to find the number of distinct // strings after performing the // given operations void numOfDistinctStrings(string arr[], int N) { // Stores the parent elements // of the sets vector parent(27);

// Stores the rank of the sets
vector<int> rank(27, 0);

for (int j = 0; j < 27; j++) {
	// Update parent[i] to i
	parent[j] = j;
}

// Stores the total characters
// traversed through the strings
vector<bool> total(26, false);

// Stores the current characters
// traversed through a string
vector<bool> current(26, false);

for (int i = 0; i < N; i++) {

	for (int j = 0; j < 26; j++) {

		// Update current[i] to false
		current[j] = false;
	}

	for (char ch : arr[i]) {

		// Update current[ch - 'a'] to true
		current[ch - 'a'] = true;
	}

	for (int j = 0; j < 26; j++) {

		// Check if current[j] is true
		if (current[j]) {

			// Update total[j] to true
			total[j] = true;

			// Add arr[i][0] - 'a' and
			// j elements to same set
			Union(parent, rank,
				arr[i][0] - 'a', j);
		}
	}
}

// Stores the count of distinct strings
int distCount = 0;
for (int i = 0; i < 26; i++) {

	// Check total[i] is true and
	// parent of i is i only
	if (total[i] && Find(parent, i) == i) {

		// Increment the value of
		// distCount by 1
		distCount++;
	}
}

// Print the value of distCount
cout << distCount << endl;

}

// Driver Code int main() { string arr[] = { "a", "ab", "b", "d" }; int N = sizeof(arr) / sizeof(arr[0]); numOfDistinctStrings(arr, N);

return 0;

}

Output: 2

C++ String Concat Example

Let's see the simple example of string concatenation using strcat() function.

#include
#include
using namespace std;
int main()
{
char key[25], buffer[25];
cout << "Enter the key string: ";
cin.getline(key, 25);
cout << "Enter the buffer string: ";
cin.getline(buffer, 25);
strcat(key, buffer);
cout << "Key = " << key << endl;
cout << "Buffer = " << buffer<<endl;
return 0;
}
Output:

Enter the key string: Welcome to Enter the buffer string: C++ Programming. Key = Welcome to C++ Programming. Buffer = C++ Programming.

C++ String Copy Example Problems:- Let's see the simple example of copy the string using strcpy() function.

#include
#include
using namespace std;
int main()
{
char key[25], buffer[25];
cout << "Enter the key string: ";
cin.getline(key, 25);
strcpy(buffer, key);
cout << "Key = "<< key << endl;
cout << "Buffer = "<< buffer<<endl;
return 0;
}
Output:

Enter the key string: C++ Tutorial Key = C++ Tutorial Buffer = C++ Tutorial

C++ String Length Example Problems-

#include
#include
using namespace std;
int main()
{
char ary[] = "Welcome to C++ Programming";
cout << "Length of String = " << strlen(ary)<<endl;
return 0;
}

Output:

Length of String = 26

Originally posted by @Manish4Kumar in https://github.com/subhamengine/DataStructures-and-Algorithm/issues/12#issuecomment-939409966