Tree Recursion in C

Back to: C Tutorials For Beginners and Professionals

Tree Recursion in C Language with Examples

In this article, I will discuss Tree Recursion in C Language with Examples. Please read our previous article discussing Nested Recursion in C Language with Examples. At the end of this article, you will understand the following pointers:

1. What is Tree Recursion in C Language?
2. Multiple Real-Time Examples to Understand Tree Recursion in C Language
3. Advantages of Tree Recursion in C Language
4. Disadvantages of Tree Recursion in C Language
5. When Would We Use Tree Recursion in C Language?

What is Tree Recursion in C Language?

Tree recursion in the C language, or in any programming language, is a form of recursion where a function makes multiple recursive calls within a single function call. This form of recursion generates a tree-like structure of calls, where each call branches out into several more calls, resembling a tree.

In tree recursion, a single call might result in more than one recursive call, and each of these calls might further branch out. This can lead to many total function calls, even for small initial inputs, making tree recursion computationally intensive. Here’s an example to illustrate tree recursion in C:

void treeRecursion(int n) {
    if (n > 0) {
        printf("%d ", n);
        treeRecursion(n - 1); // First recursive call
        treeRecursion(n - 1); // Second recursive call
    }
}

int main()
{
   // Calling the function
   treeRecursion(3);
   return 0;
}

In this example, the function treeRecursion is tree recursive. Each call with a positive n makes two recursive calls with n – 1. This results in a binary tree structure of calls. If you visualize the calls, you will notice that each level of the tree has twice as many calls as the previous level, which quickly increases the total number of calls. For treeRecursion(3), the function is called 15 times in total, forming a binary tree with 3 levels.

Tree Recursion Real-Time Examples in C Language

Tree recursion occurs when a function makes multiple recursive calls within a single function invocation. It’s called “tree” recursion because the calls form a tree-like structure of calls. This type of recursion is often used in problems where multiple subproblems must be solved independently. Here are a few examples of tree recursion in the C language:

Example: Fibonacci Series Calculation

#include <stdio.h>

// Tree recursive function to find nth Fibonacci number
int fibonacci(int n) {
    if (n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    int number = 5;
    printf("Fibonacci number at position %d is %d\n", number, fibonacci(number));
    return 0;
}

Output: Fibonacci number at position 5 is 5

Explanation:

• The fibonacci function calculates the nth number in the Fibonacci series.
• If n is 0 or 1, it’s the base case, and the function returns n.
• For n > 1, the function makes two recursive calls: fibonacci(n – 1) and fibonacci(n – 2).
• Each of these calls further branches into more calls, forming a tree-like structure.
• The value of Fibonacci (n) is the sum of the values returned by these two calls.

Example: Binary Tree Traversal

#include <stdio.h>
#include <stdlib.h>

// A basic binary tree node structure
typedef struct Node {
    int data;
    struct Node *left, *right;
} Node;

// Function to create a new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// Tree recursive function for postorder traversal
void postOrder(Node* node) {
    if (node == NULL)
        return;
    postOrder(node->left);   // Visit left subtree
    postOrder(node->right);  // Visit right subtree
    printf("%d ", node->data); // Process current node
}

int main() {
    // Creating a simple binary tree
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Postorder traversal: ");
    postOrder(root);

    return 0;
}

Output: Postorder traversal: 4 5 2 3 1

Explanation:

• This program creates a simple binary tree and performs a postorder traversal.
• The postOrder function is a tree recursive function.
• It first recursively visits the left subtree, then the right subtree, and finally processes the current node.
• The recursive calls to each node’s left and right children create a tree-like call structure.

Advantages and Disadvantages of Tree Recursion in C Language

Tree recursion in the C language, where a function makes multiple recursive calls within its body, presents a set of advantages and disadvantages that are important to consider in programming.

Advantages of Tree Recursion in C Language

• Natural Expression of Problems: Tree recursion is a natural fit for problems that inherently have a branching structure, such as tree traversals, generating permutations, or exploring decision trees.
• Simplicity in Complex Problems: It can simplify the solution of complex problems by breaking them down into smaller, more manageable subproblems, each of which is solved recursively.
• Intuitive for Divide and Conquer Algorithms: Tree recursion is ideal for divide and conquer algorithms where a problem is divided into smaller subproblems, solved independently, and combined.
• Clear and Understandable Code: For problems that naturally align with tree recursion, the resulting code can be more intuitive and easier to understand than iterative or other recursive solutions.

Disadvantages of Tree Recursion in C Language

• High Space Complexity: Tree recursion can consume a significant amount of memory due to the multiple recursive calls and the maintenance of multiple call stacks.
• Risk of Stack Overflow: Due to the potentially large number of recursive calls, stack overflow is heightened, especially if the recursion depth is large.
• Performance Overhead: The repeated function calls in tree recursion can lead to significant performance overhead, particularly if the branches of the recursion tree are deep and numerous.
• Inefficiency with Overlapping Subproblems: Tree recursion can be inefficient when there are overlapping subproblems, as it may recompute the same results multiple times. This is a common issue in naive recursive implementations of problems like the Fibonacci sequence.
• Complex Debugging and Maintenance: Debugging and maintaining tree recursive code can be challenging, especially in understanding and tracing the flow of execution through the various branches.
• Not Always Optimal: Tree recursion might not be the most efficient approach for certain problems, where iterative solutions or other forms of recursion (like tail recursion with optimization) might be more effective.

When Would We Use Tree Recursion in C Language?

Tree recursion in C, or in any programming language, refers to a type of recursion where a function makes multiple recursive calls within it. This form of recursion is often visualized as a tree, where each node represents a recursive call, branching into further calls. Here are some scenarios where tree recursion is particularly applicable:

• Exploring Multiple Possibilities: Tree recursion is useful in scenarios where an algorithm needs to explore multiple possible paths or solutions simultaneously, such as in brute-force searches or generating permutations and combinations.
• Divide and Conquer Algorithms: In divide and conquer strategies, where a problem is split into subproblems, each of which is solved independently and the solutions are combined, tree recursion can be a natural fit. Examples include merge sort and quicksort.
• Binary Tree Operations: Operations on binary trees, such as traversal (in-order, pre-order, post-order), searching, and height calculation, are naturally suited to tree recursion due to the binary tree’s inherent recursive structure.
• Backtracking Problems: In problems where backtracking is required, such as solving puzzles (like the N-Queens problem) or finding all paths in a maze, tree recursion is an effective approach.
• Dynamic Programming: While dynamic programming often uses iteration, the initial conceptualization of many dynamic programming problems is recursive, with a tree-like structure representing the various overlapping subproblems.

In the next article, I will discuss Linear Recursion in C Language with Examples. In this article, I explain Tree Recursion in C Language with Examples. I hope you enjoy this article.