Home Web Front-end JS Tutorial Introduction to methods of implementing recursive algorithms in JavaScript

Introduction to methods of implementing recursive algorithms in JavaScript

Mar 23, 2019 am 11:42 AM
javascript

This article brings you an introduction to the method of implementing recursive algorithms in JavaScript. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Let’s take a look at the definition first. A recursive algorithm converts a problem into sub-problems of the same type that are reduced in size, and each sub-problem is solved using the same algorithm. Generally speaking, a recursive algorithm is a function that calls itself to solve its subproblems.

Characteristics of recursive algorithms:

  1. calls itself during the function process.
  2. In the recursive process, there must be a clear condition to judge the end of the recursion, that is, the recursive exit.
  3. The recursive algorithm is simple but inefficient and is usually not recommended as a recommended algorithm.

The above are explanations from Baidu Encyclopedia, and they are very clear. Please consider them carefully with examples.

 Factorial

 Problem description: n! = n*(n-1)*...2*1

Code implementation:

Introduction to methods of implementing recursive algorithms in JavaScript

When we get the problem, we can first reduce the scale to similar sub-problems according to the definition. For example, n! is equal to n* (n-1)!, then (n-1)! = (n-1)*(n-2)!. Push down in this order until the exit of if. arguments.callee is used here to prevent tight coupling of function names. Here it is equivalent to factorial(n-1). Is the function implementation simple and clear? Of course, because the scale of the problem is simple, it can actually be implemented using loops. You can try it.

Fibonacci Sequence

 Problem description: 1, 1, 2, 3, 5, 8, 13, 21, 34, ....... Find the nth number.

Code implementation:

下载 (1).png

In fact, it is very simple to implement the idea just now. Through analysis, we can get the nth number, which is the sum of the first two numbers. Through this, we can continue to obtain the first two numbers we need through recursion until the condition n

 The problem of taking the stairs

 Problem description: There are n steps in the stairs. You can go up 1 step in one step or 2 steps in one step. Or level 3, count how many different moves there are.

Code implementation:

下载 (2).png

This is actually an implementation of the Fibonacci sequence. When we analyze, we can convert it into small-scale subclass problems. When reaching the last step of the designated ladder, there can be three situations: one is one step up, two is two steps up, and three is three steps up. So the overall method is F(n) = F(n-1) F(n-2) F(n-3). Then naturally it becomes their own small calculation, and the cycle continues until the judgment condition occurs.

 Greatest common divisor

Problem description: Given two numbers, if the two numbers are equal, the greatest common divisor is itself. If they are not equal, take the absolute value of the subtraction of the two numbers and compare it with the smallest of the two numbers. If they are equal, it is the greatest common denominator. If they are not equal, continue the above algorithm until they are equal.

Code implementation:

下载 (3).png

There is nothing to say, just implement it as required by the problem description. The exit of the recursion is that a equals b.

 

Tower of Hanoi

 Problem description: Everyone has played it more or less, so I won’t go into details here.

Code implementation:

下载 (4).png

Before I realized the essence of recursion, I was simply puzzled by this problem. I keep asking myself, how do I know where to go next? Later, I realized that I was actually more concerned about how to go about the last one. How do you say this? We can think from the beginning, if we only have one disk, we can make it go to column C or column B. Naturally, it can also be achieved with two disks. 3 disks is okay. Then let’s talk about the situation of 4 disks. To complete the four disks, the disk on A must be completely transferred to C. We put the first three disks as a whole on B, and then the fourth disk can be moved to C. Then we put the first three disks on C, and it was successful. The first three games can be treated as a new game, and the first two games can be treated as a whole, and so on. In this way, we only need to care about the big overall things, and other things can be solved into small-scale problems.

DichotomyQuick sort

Problem description: Use the dichotomy method to sort an array from small to large.

Code:

 下载 (5).png

Well...this is my second time writing this. This time the implementation of recursion is much clearer than last time. In fact, it is also about reducing large scale to small scale, caring about a large whole, and letting it continue to be reduced to small scale for calculation. You can check the original essay for details.

Recursion of DOM tree

Problem description: Get the tagName of all parent nodes of a node

Code implementation:

 下载 (6).png

You can probably understand it and won’t say anything. Compared with the previous Tower of Hanoi and Quick Sort, this one is quite simple, but it is closest to the practical application of our JavaScript.

This article has ended here. For more other exciting content, you can pay attention to the JavaScript Video Tutorial column on the PHP Chinese website!

The above is the detailed content of Introduction to methods of implementing recursive algorithms in JavaScript. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

How to implement an online speech recognition system using WebSocket and JavaScript How to implement an online speech recognition system using WebSocket and JavaScript Dec 17, 2023 pm 02:54 PM

How to use WebSocket and JavaScript to implement an online speech recognition system Introduction: With the continuous development of technology, speech recognition technology has become an important part of the field of artificial intelligence. The online speech recognition system based on WebSocket and JavaScript has the characteristics of low latency, real-time and cross-platform, and has become a widely used solution. This article will introduce how to use WebSocket and JavaScript to implement an online speech recognition system.

WebSocket and JavaScript: key technologies for implementing real-time monitoring systems WebSocket and JavaScript: key technologies for implementing real-time monitoring systems Dec 17, 2023 pm 05:30 PM

WebSocket and JavaScript: Key technologies for realizing real-time monitoring systems Introduction: With the rapid development of Internet technology, real-time monitoring systems have been widely used in various fields. One of the key technologies to achieve real-time monitoring is the combination of WebSocket and JavaScript. This article will introduce the application of WebSocket and JavaScript in real-time monitoring systems, give code examples, and explain their implementation principles in detail. 1. WebSocket technology

How to implement an online reservation system using WebSocket and JavaScript How to implement an online reservation system using WebSocket and JavaScript Dec 17, 2023 am 09:39 AM

How to use WebSocket and JavaScript to implement an online reservation system. In today's digital era, more and more businesses and services need to provide online reservation functions. It is crucial to implement an efficient and real-time online reservation system. This article will introduce how to use WebSocket and JavaScript to implement an online reservation system, and provide specific code examples. 1. What is WebSocket? WebSocket is a full-duplex method on a single TCP connection.

How to use JavaScript and WebSocket to implement a real-time online ordering system How to use JavaScript and WebSocket to implement a real-time online ordering system Dec 17, 2023 pm 12:09 PM

Introduction to how to use JavaScript and WebSocket to implement a real-time online ordering system: With the popularity of the Internet and the advancement of technology, more and more restaurants have begun to provide online ordering services. In order to implement a real-time online ordering system, we can use JavaScript and WebSocket technology. WebSocket is a full-duplex communication protocol based on the TCP protocol, which can realize real-time two-way communication between the client and the server. In the real-time online ordering system, when the user selects dishes and places an order

JavaScript and WebSocket: Building an efficient real-time weather forecasting system JavaScript and WebSocket: Building an efficient real-time weather forecasting system Dec 17, 2023 pm 05:13 PM

JavaScript and WebSocket: Building an efficient real-time weather forecast system Introduction: Today, the accuracy of weather forecasts is of great significance to daily life and decision-making. As technology develops, we can provide more accurate and reliable weather forecasts by obtaining weather data in real time. In this article, we will learn how to use JavaScript and WebSocket technology to build an efficient real-time weather forecast system. This article will demonstrate the implementation process through specific code examples. We

Simple JavaScript Tutorial: How to Get HTTP Status Code Simple JavaScript Tutorial: How to Get HTTP Status Code Jan 05, 2024 pm 06:08 PM

JavaScript tutorial: How to get HTTP status code, specific code examples are required. Preface: In web development, data interaction with the server is often involved. When communicating with the server, we often need to obtain the returned HTTP status code to determine whether the operation is successful, and perform corresponding processing based on different status codes. This article will teach you how to use JavaScript to obtain HTTP status codes and provide some practical code examples. Using XMLHttpRequest

How to get HTTP status code in JavaScript the easy way How to get HTTP status code in JavaScript the easy way Jan 05, 2024 pm 01:37 PM

Introduction to the method of obtaining HTTP status code in JavaScript: In front-end development, we often need to deal with the interaction with the back-end interface, and HTTP status code is a very important part of it. Understanding and obtaining HTTP status codes helps us better handle the data returned by the interface. This article will introduce how to use JavaScript to obtain HTTP status codes and provide specific code examples. 1. What is HTTP status code? HTTP status code means that when the browser initiates a request to the server, the service

How to use insertBefore in javascript How to use insertBefore in javascript Nov 24, 2023 am 11:56 AM

Usage: In JavaScript, the insertBefore() method is used to insert a new node in the DOM tree. This method requires two parameters: the new node to be inserted and the reference node (that is, the node where the new node will be inserted).

See all articles