---

Recursion in C++ is a programming technique where a function calls itself. This can be used to solve problems that can be broken down into smaller sub-problems of the same type.

Recursion is often used to solve problems involving data structures such as linked lists and trees. For example, the following function recursively prints the elements of a linked list:

void print_list(Node* head) {

  if (head == nullptr) {

    return;

  }

 

  std::cout << head->data << " ";

  print_list(head->next);

}

 

This function works by checking if the head of the linked list is null. If it is, then the function returns, because there are no more elements in the linked list. Otherwise, the function prints the data of the current node and then recursively calls itself to print the remaining elements of the linked list.

Here is an example of how to use the print_list() function:

Node* head = new Node(10);

head->next = new Node(20);

head->next->next = new Node(30);

 

print_list(head);

 

Output:

10 20 30

 

Recursion can also be used to solve more complex problems, such as sorting and searching algorithms. For example, the following function recursively sorts an array in ascending order:

void

 merge_sort(int* array, int low, int high)

 {

  if (low < high) {

    int mid = (low + high) / 2;

 

    merge_sort(array, low, mid);

    merge_sort(array, mid + 1, high);

 

    merge(array, low, mid, high);

  }

}

 

This function works by first dividing the array into two halves. Then, it recursively sorts each half. Finally, it merges the two sorted halves back into a single sorted array.

Here is an example of how to use the merge_sort() function:

int array[] = {5, 3, 2, 1, 4};

int size = sizeof(array) / sizeof(array[0]);

 

merge_sort(array, 0, size - 1);

 

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

  std::cout << array[i] << " ";

}

 

Output:

1 2 3 4 5

 

Recursion is a powerful tool that can be used to solve a wide variety of problems. However, it is important to use recursion carefully, as it can lead to stack overflows if it is not used correctly.

Here are some additional tips for using recursion:

• Make sure that the base case of your recursive function is always reached.
• Avoid using recursion for problems that can be solved more efficiently with other methods.
• Be aware of the potential for stack overflows.