Recursion - Introduction in c++

 

Recursion is a powerful concept in programming that allows for the efficient and elegant solution of certain types of problems. In this article, we will explore the basics of recursion in the C++ programming language, and discuss some of the most common applications of this technique.

At its most basic level, recursion is simply the process of calling a function within itself. When a function calls itself, it is said to be "recursive." The key to understanding recursion is to understand the concept of a "base case." A base case is a condition that, when met, will stop the function from calling itself. Without a base case, a function will continue to call itself indefinitely, resulting in an infinite loop.

One of the most common applications of recursion is in the solving of mathematical problems. For example, the factorial function, which is often used in mathematical calculations, can be implemented using recursion. The factorial of a number is the product of all the integers from that number down to 1. For example, the factorial of 5 is 5 x 4 x 3 x 2 x 1.

Here is an example of a recursive factorial function in C++:

int factorial(int n) {
 if (n == 1) {
        return 1;
    } 
 else { 
 return n * factorial(n-1);
 }
 }

In this example, the base case is when the input number is 1. In this case, the function simply returns 1. If the input number is not 1, the function calls itself with the input number decremented by 1, and multiplies the result by the original input number. This process continues until the input number reaches 1, at which point the base case is met and the function stops calling itself.

Another common application of recursion is in the traversal of data structures such as trees and linked lists. For example, consider a binary tree, where each node has two children. To traverse this tree using recursion, we would start at the root node, and recursively call the function on each child node. This process would continue until we reach the leaf nodes, at which point the function would stop calling itself.

Here is an example of a recursive function that traverses a binary tree in C++:

void traverseTree(TreeNode* root) { 
 if (root == nullptr) {
 return;
 }
    cout << root->data << endl;
 traverseTree(root->left);
 traverseTree(root->right);
}

In this example, the base case is when the input node is a nullptr. If the input node is not null, the function first prints the data of the current node, and then calls itself on the left and right child nodes. This process continues until all the nodes in the tree have been traversed.

Recursion is also commonly used in computer science problems such as searching and sorting. For example, the popular quicksort algorithm can be implemented using recursion. The quicksort algorithm works by partitioning an array into two sub-arrays, and then recursively sorting each sub-array.

Here is an example of a recursive quicksort function in C++:

void quicksort(int arr[], int low,
 int high) { 
if (low < high) {
 int pivot = partition(arr, low, high);
 quicksort(arr, low, pivot-1);
 quicksort(