Backend Development
PHP Tutorial
Detailed explanation on the use of tail recursion_PHP tutorial
Detailed explanation on the use of tail recursion_PHP tutorial
I have seen several articles about tail recursion in the past few days. I didn’t have much idea about tail recursion before, so I went back and studied tail recursion.
The concept of tail recursion
The concept of tail recursion is a subset of the recursion concept. For ordinary recursion, the cost of having to remember the recursive call stack is immeasurable. For example, the first example in the PHP section below uses PHP to write a factorial function, which causes a stack overflow error due to recursion. The purpose of tail recursion is to eliminate the shortcoming of recursive stack consumption.
From a code level, tail recursion can be explained clearly in one sentence:
The last operation of the function is the recursive call
For example, the recursive implementation of the "Fibonacci" sequence in PHP:
fibonacci.php > return fibonacci($n - 1) + fibonacci($n - 2);
}
var_dump(fibonacci(30));
This is Recursive function, but not tail recursive because the last operation of fibonacci is an addition operation.
Convert to tail recursion:
Copy code
The code is as follows:
fibonacci2 is a tail recursion, which adds two accumulators acc1 and acc2 and gives the initial value. Remember: the idea of converting recursion into tail recursion must be to increase the accumulator and reduce recursive external operations.
Tail recursion has different applications in different languages. The most commonly used one is functional programming Erlang. Almost all functions that appear recursive are modified to become tail recursive. Let’s talk about the performance and application of tail recursion in several different languages.
Tail recursion in php
Let’s do an experiment
Normal recursion:
Copy code
The code is as follows:
return factorial($n-1) * $n;
}
var_dump(factorial(100000000));
Tail recursion:
Copy code
The code is as follows:
return factorial($n-1, $acc * $n);
}
var_dump(factorial(100000000, 1));
Experimental results:
It turns out that
tail recursion has no optimization effect in PHP!
Tail recursion in C
Tail recursion optimization in C is done by the gcc compiler. Adding -O2 when compiling with gcc will optimize tail recursion
We can directly look at the generated assembly code:
(Use gdb, gcc –O2 factorial.c –o factorial; disass factorial)
Assembly generated without -O2: 
Assembly added with O2 optimization: 
Don’t be too big-headed, I also saw the assembly for the first time, but this code It’s very simple. Just search for the command online and you can roughly understand it:
function factoral( n, sum) {
while(n != 0){
sum = n * sum
n = n-1
}
return sum
}
What gcc does is indeed intelligent optimization.
If you are still interested, you can use -O3 to optimize tail recursion and view the assembly instructions
-O3’s optimization is to directly unroll the loop
Summary
The biggest advantage of modifying general linear recursion into tail recursion is that it reduces the overhead of the recursive call stack. From the PHP example, we can clearly see the impact of recursive overhead on the program. However, not all languages support tail recursion. Even languages that support tail recursion generally optimize tail recursion during the compilation phase. For example, the optimization of tail recursion in C language in the above example. When using tail recursion to optimize code, you must first understand the language's support for tail recursion.
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
1655
14
1414
52
1307
25
1253
29
1228
24
Recursive implementation of C++ functions: Is there a limit to recursion depth?
Apr 23, 2024 am 09:30 AM
The recursion depth of C++ functions is limited, and exceeding this limit will result in a stack overflow error. The limit value varies between systems and compilers, but is usually between 1,000 and 10,000. Solutions include: 1. Tail recursion optimization; 2. Tail call; 3. Iterative implementation.
BTCC tutorial: How to bind and use MetaMask wallet on BTCC exchange?
Apr 26, 2024 am 09:40 AM
MetaMask (also called Little Fox Wallet in Chinese) is a free and well-received encryption wallet software. Currently, BTCC supports binding to the MetaMask wallet. After binding, you can use the MetaMask wallet to quickly log in, store value, buy coins, etc., and you can also get 20 USDT trial bonus for the first time binding. In the BTCCMetaMask wallet tutorial, we will introduce in detail how to register and use MetaMask, and how to bind and use the Little Fox wallet in BTCC. What is MetaMask wallet? With over 30 million users, MetaMask Little Fox Wallet is one of the most popular cryptocurrency wallets today. It is free to use and can be installed on the network as an extension
How to use NetEase Mailbox Master
Mar 27, 2024 pm 05:32 PM
NetEase Mailbox, as an email address widely used by Chinese netizens, has always won the trust of users with its stable and efficient services. NetEase Mailbox Master is an email software specially created for mobile phone users. It greatly simplifies the process of sending and receiving emails and makes our email processing more convenient. So how to use NetEase Mailbox Master, and what specific functions it has. Below, the editor of this site will give you a detailed introduction, hoping to help you! First, you can search and download the NetEase Mailbox Master app in the mobile app store. Search for "NetEase Mailbox Master" in App Store or Baidu Mobile Assistant, and then follow the prompts to install it. After the download and installation is completed, we open the NetEase email account and log in. The login interface is as shown below
How to use Baidu Netdisk app
Mar 27, 2024 pm 06:46 PM
Cloud storage has become an indispensable part of our daily life and work nowadays. As one of the leading cloud storage services in China, Baidu Netdisk has won the favor of a large number of users with its powerful storage functions, efficient transmission speed and convenient operation experience. And whether you want to back up important files, share information, watch videos online, or listen to music, Baidu Cloud Disk can meet your needs. However, many users may not understand the specific use method of Baidu Netdisk app, so this tutorial will introduce in detail how to use Baidu Netdisk app. Users who are still confused can follow this article to learn more. ! How to use Baidu Cloud Network Disk: 1. Installation First, when downloading and installing Baidu Cloud software, please select the custom installation option.
Do C++ lambda expressions support recursion?
Apr 17, 2024 pm 09:06 PM
Yes, C++ Lambda expressions can support recursion by using std::function: Use std::function to capture a reference to a Lambda expression. With a captured reference, a Lambda expression can call itself recursively.
Recursive implementation of C++ functions: Comparative analysis of recursive and non-recursive algorithms?
Apr 22, 2024 pm 03:18 PM
The recursive algorithm solves structured problems through function self-calling. The advantage is that it is simple and easy to understand, but the disadvantage is that it is less efficient and may cause stack overflow. The non-recursive algorithm avoids recursion by explicitly managing the stack data structure. The advantage is that it is more efficient and avoids the stack. Overflow, the disadvantage is that the code may be more complex. The choice of recursive or non-recursive depends on the problem and the specific constraints of the implementation.
How to use Xiaomi Auto app
Apr 01, 2024 pm 09:19 PM
Xiaomi car software provides remote car control functions, allowing users to remotely control the vehicle through mobile phones or computers, such as opening and closing the vehicle's doors and windows, starting the engine, controlling the vehicle's air conditioner and audio, etc. The following is the use and content of this software, let's learn about it together . Comprehensive list of Xiaomi Auto app functions and usage methods 1. The Xiaomi Auto app was launched on the Apple AppStore on March 25, and can now be downloaded from the app store on Android phones; Car purchase: Learn about the core highlights and technical parameters of Xiaomi Auto, and make an appointment for a test drive. Configure and order your Xiaomi car, and support online processing of car pickup to-do items. 3. Community: Understand Xiaomi Auto brand information, exchange car experience, and share wonderful car life; 4. Car control: The mobile phone is the remote control, remote control, real-time security, easy
How to use spaces correctly in Go
Mar 29, 2024 pm 03:42 PM
Go language is a simple, efficient, and highly concurrency programming language. It is an open source language developed by Google. In the Go language, the use of spaces is very important, it can improve the readability and maintainability of the code. This article will introduce how to use spaces correctly in Go language and provide specific code examples. Why you need to use spaces correctly In the programming process, the use of spaces is very important for the readability and beauty of the code. Appropriate use of spaces can make code clearer and easier to read, thus reducing
