Recusion from Tree Perspective

Understanding Recusion from the Tree Perspective

Fibonacci Sequence

The Fibonacci function is defined as:

$$fib(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ fib(n-1) + fib(n-2) & \text{if } n > 1 \end{cases}$$

Recusive Approach:

int fib(int n) {
    if (n < 2) {
        return n;
    }
    return fib(n-1) + fib(n-2);
}

Permutation Problem

You are given an input array nums with n distinct elements. You are asked to return all possible permutations of these elements.

For example, given nums = [1,2,3], the algorithm returns the following 6 permutations:

[1,2,3], [1,3,2],
[2,1,3], [2,3,1],
[3,1,2], [3,2,1]

Recusive Part:

// Permutations algorithm main structure
void backtrack(int[] nums, List<Integer> track) {
    if (track.size() == nums.length) {
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        backtrack(nums, track);
    }
}

// Multi-fork tree traversal function
void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    for (TreeNode child : root.children) {
        traverse(child);
    }
}

Two Mindsets for Writing Recusive Algorithms

1. Problem Decomposition:

   Important

   This recursive function must have a clear definition, explaining what the function parameters mean and what result it returns.

   • Example 1 - Fibonacci Sequence:

     • Breaking a larger problem fib(5) into smaller subproblems fib(4) and fib(3)

         // Definition: Input a non-negative integer n, return the nth number in the Fibonacci sequence
         int fib(int n) {
             if (n < 2) {
                 return n;
             }
             // Use the definition to calculate the first two Fibonacci numbers (subproblems)
             int fib_n_1 = fib(n - 1);
             int fib_n_2 = fib(n - 2);
     
             // Use the answers of subproblems to calculate the original problem
             return fib_n_1 + fib_n_2;
         }

   • Example 2 - LeetCode Problem: 104."Maximum Depth of Binary Tree"

     • Decomposing the problem: to calculate the maximum depth of the entire tree, first calculate the maximum depth of the left and right subtrees, take the maximum of the two values and add one, which gives the maximum depth of the entire tree
     $$\text{maxDepth}(\text{root}) = \begin{cases} 0 & \text{if } \text{root} = \text{null} \\ \max(\text{maxDepth}(\text{root.left}), \text{maxDepth}(\text{root.right})) + 1 & \text{otherwise} \end{cases}$$

         // Divide and Conquer Idea
         class Solution {
             // Definition: Given a node, return the maximum depth of the binary tree rooted at that node
             public int maxDepth(TreeNode root) {
                 if (root == null) {
                     return 0;
                 }
                 // Use the definition to calculate the maximum depth of the left and right subtrees
                 int leftMax = maxDepth(root.left);
                 int rightMax = maxDepth(root.right);
     
                 // Derive the maximum depth of the original binary tree based
                 // on the maximum depth of the left and right subtrees
                 // The maximum depth of the entire tree is the
                 // maximum of the left and right subtree depths,
                 // plus one for the root node itself
                 return 1 + Math.max(leftMax, rightMax);
             }
         }

2. Traversal Approach

   Important

   If you want to write a recursive algorithm using the "traversal" approach, you need a traversal function without a return value, which collects results during the traversal.

   • Just note that the backtrack function has no return value and no explicit definition. It acts like a for loop, simply traversing the recursive tree and collecting results from the leaf nodes

       // Permutations algorithm main structure
       // Global variable, store the state of backtrack function traversal
       List<List<Integer>> res = new LinkedList<>();
       List<Integer> track = new LinkedList<>();
   
       // Recursion tree traversal function
       void backtrack(int[] nums, List<Integer> track) {
           if (track.size() == nums.length) {
               // Reach the leaf node, collect the result
               res.add(new LinkedList<>(track));
               return;
           }
           for (int i = 0; i < nums.length; i++) {
               // Make a choice
               track.add(nums[i]);
   
               backtrack(nums, track);
   
               // Undo the choice
               track.removeLast();
           }
       }

Summary

Steps to write a recursive algorithm:

1. First, can this problem be abstracted into a tree structure? If so, a recursive algorithm is needed.

2. If a recursive algorithm is needed, consider the two thinking modes of "traversal" and "problem decomposition" to determine which is more suitable for the problem.

3. If using the "problem decomposition" mode, clearly define the recursive function and use this definition to break down the problem and derive the solution from subproblems; if using the "traversal" mode, use a non-returning recursive function to purely traverse the recursive tree and collect the target results.