Algorithm Diagram 2 (recursion and call stack in memory)

Graphic algorithm 2

Recursion – An elegant solution to a problem

Conclusion:

• Recursive conditions: Conditions on which recursive functions call themselves
• Baseline condition: Condition under which a recursive function terminates calling itself
• Recursion only makes the solution clearer, and has no performance advantage.(Tail recursion is not considered)
  

  In recursive implementation, the system realallocates memory space to variables (normal loop is overwrite).

  Recursion only frees stack memory when it reaches the end function (baseline condition)

  So recursion too many times can cause memory allocation to crash

Note: It is possible to avoid memory crashes by using tail recursion as part of advanced recursion, but this is rarely used due to language and scenario constraints, so it is not considered here.

True knowledge comes from practice

• Test cases are used to verify that looping performs better than recursion in most scenarios
• In order toJSFor example, use a common debugging function to measure the execution time of a JS script

Console.time () starts the code execution timing

Console.timeend () stops the timing and prints out the execution time of the script.

/ * -- -- -- -- -- -- -- -- -- -- Recursive -- -- -- -- -- -- -- -- -- -- -- - * / console in time (' testRecursive) function Recursive (num) {if (num > 1) {return num * Recursive(num - 1) } else return num; } Recursive(8000); The console. TimeEnd (' testRecursive) / * -- -- -- -- -- -- -- -- -- -- the traditional cycle -- -- -- -- -- -- -- -- -- -- -- - * / console. Time (' testFor) var flag = 1; for (var x = 8000; x > 1; x--) { flag *= x; } console.timeEnd('testFor')Copy the code

How recursion works: Recursion is implemented by calling the function itself repeatedly, each time saving local variables, parameters, return values, etc., which affects the efficiency of code execution.

The stack: the call stack(the call stack)Is a very important concept in programming.

The computer internally uses stacks called call stacks

The main function of the call stack is to save the return address of the call.

• For example

function Poo(name){ console.log(`Hi,I'M ${name}`); getHobby(name); Bye(name); } function getHobby (name){console.log(' ${name} hobby is programming ~ '); } function Bye(name){console.log(' welcome to ${name} next time '); } Poo('potato')Copy the code

1. In this function, when Poo() is called, the computer first allocates a block of memory for the function call
2. So if I use this memory, first of all, variables nameIs set to potato, which needs to be stored in memory

• Whenever a function is called, the computer stores the value of the variable involved in the function into memory like this

  Initial call to Poo(‘potato’)

  • performPooFunction, the assigned value stores the variable in memory
  • Then print Hi,I'M potato

  	Poo
  name	potato

  • Call again getHobby(name)The computer also allocates memory for it, with the second block above the firstPress (stack)

  	getHobby
  name	potato
  	Poo
  name	potato

  • getHobby(name)Done, print'Potato's hobby is programming'The function call returns, and the memory block at the top of the stack pops up

  	getHobby
  name	potato

  • At this point, the upper memory block is separated (pop)

  	Poo
  name	potato

  The function at the top of the stack is Poo(), which means it’s back to the function Poo(‘potato’), which is only partially executed overall

  • Note: This is an important concept. When another function is called from within a function, the current function is suspended and in an unfinished state. All of the variable values of the function are still in memory getHobby(name)Back to the Poo('potato')“And then proceed from where you left off.

  Then call Bye(name) to add the memory block for this function at the top of the stack, repeat the steps above, and pop it off the top of the stack after printing.

  	Bye
  name	potato
  	Poo
  name	potato

  This stack is used to store variables for multiple functions and is therefore called the call stack

conclusion

It can be seen from the above characteristics:

• Recursion has no performance advantage, just easier code to read.
• In actual use scenarios, the call stack may be very long and occupy a large amount of memory, resulting in memory crash

You may also be interested in the following

• # Diagram Algorithm 1 (arrays and linked lists in memory)
• # Algorithm Diagram 3 (Quicksort and Euclid)
• # Algorithm Figure 4 (hash table and loading factor)
• # JavaScript Language Essence
• How are some of the apis implemented in # VUE3.0?
• JavaScript reads local file configuration (compatible with lower IE versions)
• # What do you ask about the front end of one year’s work experience?