In this manner, the counting process is not truly complete until all the books have been counted, including the recently added one. This concept is known as "tail recursion", where it involves initiating a fresh iteration of counting from the start, incorporating additional data that has been gathered along the way.
Uses of Tail Recursion:
Tail recursion is primarily employed in various computations. Some examples include:
Calculating Factorials:
As previously discussed, computing the factorial of a number through tail recursion is a typical illustration. The function continuously multiplies the number by an accumulator as it progresses through each recursive invocation.
Calculating Exponentiation:
Another instance involves calculating the exponentiation of a value utilizing tail recursion. This recursive function iteratively multiplies the base by itself, decrementing the exponent with each iteration until it reaches zero.
Finding Fibonacci Numbers:
Calculating Fibonacci numbers with tail recursion is a viable approach. The function computes the total of the preceding two Fibonacci numbers and forwards them as parameters in the subsequent recursive invocation.
Binary Search in Sorted Array:
Deploying binary search with tail recursion is a viable approach. The function evaluates the target element against the middle element and then proceeds to search the left or right subarray by making recursive calls accordingly.
Reversing a List:
Reversing a list through tail recursion can be achieved where the function appends the initial element to the reversed sublist during each recursive invocation.
String Reversal:
Reversing a string using tail recursion can also be achieved. In each recursive call, the function appends the initial character of the string to the reversed substring.
Counting List Elements:
Calculating the quantity of items in a list through tail recursion serves as another instance. The function adds one to a counter for each item and then invokes itself recursively with the remaining part of the list.
Tree Traversal:
In specific scenarios, tree traversal techniques such as post-order traversal can be executed through tail recursion. This approach involves exploring the left and right subtrees before handling the current node in a tail-recursive fashion.
Generating Permutations:
Creating permutations of a set through tail recursion is achievable by swapping elements within the set and then recursively producing permutations for the remaining elements.
Generating Combinations:
Creating permutations of elements through tail recursion is also achievable. This function iterates recursively to generate permutations by either incorporating or excluding each element.
Example of the tail recursion in C:
Example 1: Printing factorial of a number using tail recursion.
#include <stdio.h>
int factorial(int n, int accumulator) {
if (n == 0) {
return accumulator;
} else {
return factorial(n - 1, n * accumulator);
}
}
int main() {
int n = 5;
int result = factorial(n, 1);
printf("Factorial of %u is %u\n", n, result);
return 0;
}
Output:
Factorial of %u is %u
Explanation:
In this instance, the function initiates by verifying whether the existing value of "n" equals 0. Should this condition be met, the function ceases further multiplication and proceeds to return the accumulated "accumulator" value. This specific scenario serves as the fundamental case that halts the recursive process.
If the value of "n" is not equal to 0, the function computes the multiplication of "n" and the "accumulator". Subsequently, it initiates a recursive call to itself, passing a reduced value of "n" and the updated result as the new "accumulator".
The procedure continues repeating until "n" reaches 0. With each iteration, the function invokes itself, incrementally progressing towards problem resolution. This recursive invocation occurs as the final step within the function, a concept known as tail recursion.
Tail recursion is efficient due to its optimized memory usage. By concentrating solely on the current operation and the updated outcome, the system doesn't have to retain a multitude of previous states. This approach is akin to performing calculations while simultaneously keeping track of them.
Example 2: Printing Fibonacci sequence using tail recursion.
#include <stdio.h>
int fibonacci(int n, int a, int b) {
if (n == 0) {
return a;
} else {
return fibonacci(n - 1, b, a + b);
}
}
int main() {
int n = 6;
int result = fibonacci(n, 0, 1);
printf("Fibonacci number at index %u is %u\n", n, result);
return 0;
}
Output:
Factorial of %u is %u
Explanation:
In this instance, the software defines a function called "fibonacci" to locate a particular number within the Fibonacci series. The function requires three parameters: "n" (representing the position of the desired number), "a" (the initial number in the sequence), and "b" (the second number in the sequence).
Within the "fibonacci" function, there exists a check to verify whether the input "n" equals 0. If this condition is true, it signifies that the desired number in the Fibonacci sequence has been reached. Consequently, the function proceeds to return the value of "a".
If the value of "n" is not zero, the function is designed to determine the subsequent number in the Fibonacci series. This is achieved by recursively invoking itself, with a modified configuration. The variable "a" is reassigned to the value of "b" (representing the second number in the sequence), while "b" is updated to the sum of the original "a" and "b" (indicating the third number in the sequence).
This procedure continues iteratively until the value of "n" reaches zero. Each recursive invocation brings you nearer to determining the specific Fibonacci number you seek.
In the "main" function of the program, the variable "n" is initialized to 6, indicating the desire to calculate the 6th Fibonacci number. Subsequently, the "fibonacci" function is invoked with the initial values 0 and 1.
The outcome of the "fibonacci" function is saved in the "result" variable. Ultimately, you display the values of "n" and the corresponding Fibonacci number at that specific index.
In basic language, this code functions akin to a journey through the Fibonacci sequence, steadily progressing towards the desired number. For instance, when "n = 6", the code will yield the 6th Fibonacci number, which is 8.
Example 3: Printing the combinations
#include <stdio.h>
void generateCombinations(int arr[], int n, int index, int combination[], int k, int start) {
if (index == k) {
for (int i = 0; i< k; i++) {
printf("%d ", combination[i]);
}
printf("\n");
return;
}
for (int i = start; i< n; i++) {
combination[index] = arr[i];
generateCombinations(arr, n, index + 1, combination, k, i + 1);
}
}
int main() {
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2; // Choose k elements
int combination[k];
printf("Combinations:\n");
generateCombinations(arr, n, 0, combination, k, 0);
return 0;
}
Output:
Factorial of %u is %u
Explanation:
In this instance, the code utilizes the "generateCombinations" function to generate various combinations. For this function to operate correctly, it requires several parameters: the initial set of numbers ("arr"), the total count of numbers available ("n"), the present position within the combination ("index"), the evolving combination ("combination"), the preferred size of each combination ("k"), and the starting point for selecting numbers ("start").
Within the "generateCombinations" function, there is a validation to determine if a sufficient number of values has been gathered to form a complete combination. In case this condition is met, indicating the availability of a comprehensive set, the associated numbers are displayed, and the process is reset to explore additional combinations.
If an insufficient number of values have been gathered, the function will commence selecting numbers sequentially. It will select a value from the point where the previous selection ended and append it to the "combination". Subsequently, a recursive call is made with an additional number in the combination and a revised starting position for the subsequent number selection process.
This procedure repeats continuously, as the function iterates through various numbers and generates diverse combinations until it gathers adequate numbers for a full set.
In the "main" function within the code, an array containing the numbers 1, 2, 3, and 4 is present, and the objective is to generate pairs of numbers. Subsequently, an array named "combination" is initialized to hold each pair, following which the "generateCombinations" function is invoked to initiate the procedure.
The function iterates over every possible pair of numbers given, generating combinations of size 2, and then displays them.
Example 4: Printing permutations using tail recursion:
#include <stdio.h>
void swap(char* a, char* b) {
char temp = *a;
*a = *b;
*b = temp;
}
void generatePermutations(char str[], int start, int end) {
if (start == end) {
printf("%s\n", str);
return;
}
for (int i = start; i<= end; i++) {
swap(&str[start], &str[i]);
generatePermutations(str, start + 1, end);
swap(&str[start], &str[i]); // Backtrack
}
}
int main() {
char str[] = "ABC";
int n = sizeof(str) - 1;
printf("Permutations:\n");
generatePermutations(str, 0, n - 1);
return 0;
}
Output:
Factorial of %u is %u
Explanation:
In this instance, the software utilizes a function named "swap" to interchange the positions of two characters. This process is akin to shuffling the positions of two cards within a deck.
Following that, there is an additional function named "generatePermutations". This function accepts a string composed of letters denoted as "str", the initial position for organizing the letters labeled as "start", and the concluding position referred to as "end".
Within the "generatePermutations" function, there exists a validation to determine if the process of rearranging the characters has been completed. If this condition is met, it signifies the successful creation of a fresh arrangement, prompting its output.
If the process is not complete, the function initiates the exchange of letters. It swaps a single letter with another one before recursively invoking itself with the subsequent position to rearrange and retaining the final position.
This procedure continues to occur, with the function exchanging and reorganizing letters in various manners, generating fresh configurations with each iteration.
After exhausting all potential configurations, the function "backtracks" is triggered. This action involves reversing the most recent swap, allowing for the exploration of alternative swaps in the subsequent iteration of configurations.
In the main function, the generatePermutations function is invoked to calculate the total number of permutations for the letters A, B, and C within the program.
The function iterates over every conceivable permutation of the characters and displays them one by one.
Example 5: Post-order tree traversal using tail recursion.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* left;
struct Node* right;
};
void postOrderTraversal(struct Node* root) {
if (root == NULL) {
return;
}
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
printf("Post-order traversal: ");
postOrderTraversal(root);
return 0;
}
Output:
Factorial of %u is %u
Explanation:
struct Node:
This statement introduces a fresh arrangement known as "Node" , which encompasses a pair of pointers designated as the left and right. These pointers correspond to the left and right offspring of the specified tree. In this scenario, a "Node" comprises an integer value ("data") along with two "pointers" directing to additional "Nodes" named "left" and "right" .
void postOrderTraversal(struct Node* root):
This statement declares a function called "postOrderTraversal". It accepts an input of a "Node" pointer named "root". This function aids in navigating the nodes of a "tree", a unique data structure. It employs a method known as "post-order", where it traverses to the left first, then to the right, and lastly deals with the current node.
if (root == NULL) { return; }:
This statement verifies if the current node, referred to as the "root" node, is either empty (NULL) or not. If the node is empty, indicating the end of the branch in the tree, the process halts at this point.
Execute postOrderTraversal method on the left child of the root node followed by the right child of the root node.
These statements are pivotal for the program's execution. The function recursively invokes itself two times, once for the left subtree ("root->left") and once for the right subtree ("root->right"). This approach ensures thorough traversal of the entire tree through recursion.
printf("%d ", root->data);:
This statement displays the "data" contained in the present node. In this instance, it represents the numerical value stored within the node. The data is outputted subsequent to traversing through both the left and right branches due to the post-order traversal method.
struct Node* createNode(int data):
This function, named "createNode", is designed to accept an integer parameter called "data" and generate a fresh "Node" containing this specified data. Its purpose is to facilitate the creation of new nodes intended for the tree structure.
newNode->data = data;:
This line assigns the "data" value of the freshly generated node to the specified "data" value.
newNode->left = NULL; and newNode->right = NULL;:
These statements assign NULL values to the left and right pointers of the newly created node, indicating that it is currently not linked to any other nodes.
int main {:
This is the point where program execution begins. It represents the "main" function within the program structure.
struct Node* root = createNode(1);:
This code snippet instantiates a fresh instance of a "Node" object containing the integer value 1, which is then assigned to a pointer named "root".
Assign the left child of the root node to a newly created node with a value of 2, and assign the right child of the root node to a newly created node with a value of 3.
These instructions generate two additional nodes containing values 2 and 3, which are then linked to the "root" node on its left and right sides.
Create a new node with the value of 4 for the left child of the left child of the root, and create a new node with the value of 5 for the right child of the left child of the root.
These instructions generate a pair of nodes containing 4 and 5 as values, then link them to the left of the "root's" left node, resembling the construction of a miniature tree.
printf("Post-order traversal: ");:
This statement displays a message to provide a preview of the upcoming content.
postOrderTraversal(root);:
Invoke the "postOrderTraversal" method passing the "root" node as the initial reference point. This function systematically traverses the complete tree using a post-order approach.