❝

Know what you are and why you are

preface

Recursion is more or less common when writing business code, such as traversing a tree structure.

This article will explain recursion through the classic case: Finding Fibonacci number to explain recursion, through the way of drawing recursion tree to explain its time complexity and space complexity as well as the implementation order of recursion, welcome interested developers to read this article.

Basic understanding of recursion

  • Image understanding

    • The function will call itself
    • The parameters of the function converge to smaller with each call

  • Real understanding

    • Turn a big problem into one or n small problems
    • Use the same logic to solve these problems
    • And finally put it all together, put it all together

  • The specific implementation

    • Write the Base case first, define the baseline condition, judge whether it is the minimum number problem, avoid the endless loop
    • Recursive rule: Recursive rule

Instance analysis

Let’s use an example to illustrate recursion.

Find the Fibonacci number

Finding Fibonacci numbers at a particular location is easy to do recursively, so let’s first look at the concept of Fibonacci numbers.

  • The Fibonacci number at position zero is zero
  • The Fibonacci number for position one is one
  • The Fibonacci number at n(n>1) is Fibonacci number at n-1 + Fibonacci number at n-2

Once we know how to calculate Fibonacci numbers, we can do it recursively.

We can apply the above recursive understanding to the Fibonacci number, the implementation ideas and implementation code is as follows:

  • Base case: The Fibonacci number at position 0 is 0 and the Fibonacci number at position 1 is 1. That is, n === 0 return 0, n === 1 return 1;
  • Recursive rule: value of position n = value of position N-1 + value of position n-2, i.e. FibonacciNumbers (N-1) + fibonacciNumbers(n-2);
const fibonacciNumbers = function(n){
    // base case
    if(n === 0) {        return 0;
    }else if(n === 1) { return 1;  }   // Recursive rule  return fibonacciNumbers(n - 1) + fibonacciNumbers( n - 2); } Copy the code

Time complexity analysis

We converted the above code execution process into the recursion tree as shown in the figure below. After observing the nodes in the binary tree, we found the following rules:

  1. Layer 0 has 1 node, layer 1 has 2 nodes, layer 2 has 4 nodes, layer 3… At the NTH layer, each layer has twice as many nodes as the previous layer.

  2. That is, 1 + 2 + 4 + 8 + 2^(n-1), sum of geometric sequence: 2^n, time complexity: O(2^n).

  3. The total number of nodes in the last layer far exceeds the total number of nodes in all other layers.

  4. The time complexity depends on how many nodes there are in the recursion tree.

  5. The time complexity of all recursions can be analyzed by recursion trees.


Spatial complexity analysis

To analyze the spatial complexity, we can analyze it through the recursive execution order. We sorted the execution order of the above codes into a recursive graph to indicate their execution order, and found the following rules:

  1. Due to the influence of von Neumann system, recursion tree is executed depth-first. Namely: follow a line to the end (honey orange line).

  2. The bp of each layer in the figure is called break point. When each layer is executed to BP, the variable (n) of the current layer will be recorded and put into the Call Stack.

  3. Since each layer in the recursion tree is executed with a Call Stack operation that puts in the variable (n) of the current layer, the number of Call stacks in the recursion tree depends on the number of layers in the recursion tree, and hence the spatial complexity is O(n).

  4. Space complexity is not related to the total number of nodes, but is directly related to the total number of layers that coexist in the Call Stack.

  5. The spatial complexity of all recursions can be analyzed by recursion trees.


Execution sequence analysis

The order of execution of the above recursive graph is shown below, and the next step is to analyze what is done in each step with the cost:

  • When the function executes to return fibonacciNumbers(n-1) + fibonacciNumbers(n-2), because of the von Neumann system, it doesn’t execute in parallel, it executes fibonacciNumbers(n-1) first, When the baseline condition is triggered, return to the previous level, retrieve the value of n stored in the call Stack at the previous level, and then execute the fibonacciNumbers(n-2) function to calculate the value of its right subtree.
  • So he will first execute fibonacciNumbers(n-1), that is :F(4) => F(3)… =>F1 (line 1 of the figure)
  • When it reaches F(1), n = 1 triggers the baseline condition return 1 to the level above F(2), which is line 2 in the figure
  • When you return to layer F(2), fetch the value of n stored in the current layer’s Call Stack and execute the fibonacciNumbers(n-2) function to F(0), line 3 in the figure
  • At this point, the value of n in F(0) is 0, triggering the baseline condition and returning 0, which is line 4 in the figure
  • At this point, the values of the left and right subtrees of node (2) are calculated, so we can execute the function fibonacciNumbers(n-1) + fibonacciNumbers(n-2), add the values of the left and right subtrees, and obtain the value of F(2). Then return the level above F(3), line 5 in the figure.
  • When returning to F(3), as in step 3, obtain the value of its right subtree, then repeat steps 3 to 6 until the value of F(3) and F(2) is calculated, and the value of F(4) is obtained by adding them. At this time, the value at F(4) is the Fibonacci number we need, namely lines 6 to 16 in the figure.

Write in the last

  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow 😊
  • This article was first published in nuggets. Reprint is prohibited without permission 💌