Two common algorithms and optimizations from Fibonacci sequence

Welcome to Github

The Fibonacci sequence is a very classical mathematical concept, first proposed by The Italian mathematician Leonardo Fibonacci in 1202. Its recursive method is defined as: F(1) = 1, F(2) = 1, F(n) = F(n-1) + F(n-2) (n ≥ 3, n ∈ n) *. This paper mainly discusses its solution from two kinds of algorithms, namely recursion and recursion, and two kinds of optimization methods: memorization and function tail call optimization.

A recursive algorithm

const fib = function(N) {
  if (N <= 1) return N
  return fib(N - 1) + fib(N - 2);
};
Copy the code

Recursion algorithm is an algorithm that calls its own functions or methods directly or indirectly. The essence of recursive algorithm is to decompose the problem into subproblems of the same kind in reduced size, and then recursively call methods to represent the solution of the problem.

Characteristics of recursive algorithm to solve problems:

• Recursion is a method that calls itself.
• When using an incremental regression strategy, there must be an explicit recursive end condition, called a recursive exit.
• Recursive algorithm is usually very simple to solve problems, but the efficiency of recursive algorithm is low. So it is generally not recommended to use recursive algorithms to design programs.
• In the recursive call process, the system opens up a stack for each layer of return points, local quantities, etc. Too many recursion times are easy to cause stack overflow, so it is generally not recommended to use recursive algorithm to design programs.

The recursive exit of the above algorithm is if (N <= 1) return N, indicating that the first and second bits of fib start from 0 and 1 respectively. Suppose we use this algorithm to solve fib when N is 3, then the recursion process is as follows:

// fib(3) returns the sum of fib(2) and fib(1)
fib(3) = fib(2) + fib(1);
// fib(2) returns the sum of fib(1) and fib(0)
fib(2) = fib(1) + fib(0);
// fib(1) and fib(0) trigger recursive exit conditions, returning 1 and 0 respectively
fib(1) = 1; fib(0) = 0;
Copy the code

Through the recursive process above, fib(3) is finally converted to the solution of fib(1) + FIB (0) + FIB (1).

Recursion is not optimal and can lead to stack overflow problems.

Here is the leetcode execution time and memory consumption:

Time complexity: O(2^N).

Space complexity: O(N).

Function tail call optimization

const fib = function(N) {
  return calc(N, 0.1);   
};

const calc = function(count, n, m) {
  if (count === 0) return n;
  return calc(count - 1, m, n + m);
}
Copy the code

Tail Call is an important concept of functional programming. It refers to the situation in which the last action of a function is to Call the function, and function Tail optimization is to optimize the stack space of the function through the Tail Call.

Principle: When a function is called, a call frame is formed in memory, which stores information such as the call location and internal variables. If the function itself is recursively called, all the call records will form a Call stack. Complex nested recursion takes up a lot of stack space. When the compiler detects that a function call is tail-recursive, it overwrites the current active record rather than creating a new one on the stack. By overwriting the current stack frame rather than adding one on top of it, the amount of stack space used is greatly reduced, making the actual run more efficient.

All of the above code satisfies the “last action is to call a function” situation, so it is a tail call. Different from the recursive algorithm, the tail-call optimization passes the fib(0) and fib(1) values to the CALC method as the default parameter values, and executes the addition operation of the two items before the recursive algorithm returns to fib in the function parameter, which achieves tail-call optimization.

Here is the leetcode result:

Time complexity: O(2^N).

Space complexity: O(1).

Memory,

const fib = function(N) {
  return memo(N);
};

function memo(N, arr = []) {
  if (N <= 1) return N;
  if(! arr[N]) arr[N] = memo(N -1) + memo(N - 2);
  return arr[N];
}
Copy the code

In recursive algorithm, there is the problem of repeated calculation. For example, fib(2) will be repeated twice when solving FIB (4). While there is not a particularly large performance penalty at very small N and may be superior to mnemonization, which opens up new space to store calculated values, the advantages of mnemonization are shown when working with large data.

The above code adds an ARR array to store the calculated result. If the arR already stores the corresponding value, the calculation is not repeated and the stored result is returned directly.

In fact, there is a better algorithm for solving the Fibonacci sequence than memorization, and that is recursion.

Time complexity: O(N).

Space complexity: O(N).

recursive

const fib = function(N) {
  if (N <= 1) return N;
  
  const arr = [];
  arr[0] = 0;
  arr[1] = 1;
  for (let i = 2; i <= N; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[N];
};
Copy the code

The Recursive is given an initial set of values, then computed according to The rules and finally achieved The desired result. If recursion is going from unknown to known, recursion is going from known to unknown.

Recursion is more consistent with human thinking habits. The value of FIB (2) can be calculated from fib(0) and FIB (1), and the value of FIB (3) can be calculated after knowing the value of FIB (1) and FIB (2). And so on, you can calculate the result for all the values. Compared with recursion, recursion does not have the problem of double calculation and is better in operation efficiency.

Here is the leetcode result:

Time complexity: O(N).

Space complexity: O(1)

reference

Recursive algorithm in detail