递归算法事例
一．例子（用从C＋＋描述）：
行号 程序
0 p (int w)
1 {if（ w>o）
2 { cout
3 p(w-1);
4 p(w-1);
5 }
6 }
结束
执行语句 p(4) 后的打印结果：4 3 2 1 1 2 1 1 3 2 1 1 2 1 1
二．说明：
1．递归调用与普通的调用原理相同，只不过是每次调用的函数都是自己本身。
2．我们完全可以自己编程设置堆栈（用户堆栈），来实现与“递归调用”相同的功能。
3． 3.在“递归调用”时，系统会自动设置和管理堆栈（系统堆栈），而
无需我们的干预，但这同时增加了“递归调用”的神秘性。为了更好
地 地理解“递归调用”，现将系统堆栈以表格的方式表示出来。
4．对于“堆栈”格式的一些说明
堆栈的格式为：
方格a
方格b
方格c
函数调用完返回的行号
调用的函数
W 的值
每调用一次函数就“入栈”一次；函数执行完了，就“出栈”一次
三．程序解释：
1．开始调用p(4)，此时执行的语句有：1、2、3
结束
P(4)
4
执行p(4)的语句2：cout
但是由于语句3，在执行过程中还要调用p(3)，只有p(3)执行完了，才能继续执行p(4)。
2．开始调用P(3)，此时执行的语句有：1、2、3
4
P(3)
3
结束
P(4)
4
当p（3）执行完了，就会执行p(4)中的语句4（所以在方格a中，填“4”）。
执行p(3)的语句2：cout
同上面的情况相同，当执行到语句3，还要调用p(2)，只有p(2)执行完了，才能继续执行p(3)。
3．开始调用P(2)，此时执行的语句有：1、2、3
4
P(2)
2
4
P(3)
3
结束
P(4)
4
执行p(2)的语句2：cout
同上面的情况相同，当执行到语句3，还要调用p(1)，只有p(1)执行完了，才能继续执行p(2)。
4．开始调用P(1)，此时执行的语句有：1、2、3
4
P(1)
1
4
P(2)
2
4
P(3)
3
结束
P(4)
4
执行p(2)的语句2：cout
同上面的情况相同，当执行到语句3，还要调用p(0)，只有p(0)执行完了，才能继续执行p(1)。
5．开始调用P(0)，此时执行的语句有：1
4
P(0)
0
4
P(1)
1
4
P(2)
2
4
P(3)
3
结束
P(4)
4
因为w＝0不满足语句1，所以直接跳到语句5、6，从而p(0)执行完毕，p(0)要进行“出栈”操作。
6．此时执行的语句有：4
4
P(1)
1
4
P(2)
2
4
P(3)
3
结束
P(4)
4
由于p(0)执行完成，且p(0)的方格a中为4，因此继续执行p(1)的语句4 ：p(w-1)； 又由于p(1)方格c中w值为1，所以调用p(0)。
7．开始调用p(0)
5
P(0)
0
4
P(1)
1
4
P(2)
2
4
P(3)
3
结束
P(4)
4
当p（0）执行完了，就会执行p(1)中的语句5（所以在方格a中，填“5”）。
因为w＝0不满足语句1，所以直接跳到语句5、6，从而p(0)执行完毕，p(0)要进行“出栈”操作。
8．此时执行的语句有：5
4
P(1)
1
4
P(2)
2
4
P(3)
3
结束
P(4)
4
由于p(0)执行完成，且p(0)的方格a中为5，因此继续执行p(1)的语句5 （最后一句），所以p(1)执行完毕，p(1)要进行“出栈”操作。
9．
4
P(2)
2
4
P(3)
3
结束
P(4)
4
由于p(1)执行完成，且p(1)的方格a中为4，因此继续执行p(2)的语句4 ：p(w-1)； 又由于p(2)方格c中w值为2，所以调用p(1)。
10．开始调用P(1)，此时执行的语句有：1、2、3
5
P(1)
1
4
P(2)
2
4
P(3)
3
结束
P(4)
4
当p（1）执行完了，就会执行p(2)中的语句5（所以在方格a中，填“5”）。
执行p(1)的语句2：cout
当执行到语句3，还要调用p(0)，只有p(0)执行完了，才能继续执行p(1)。
11．始调用P(0)，此时执行的语句有：1
4
P(0)
0
5
P(1)
1
4
P(2)
2
4
P(3)
3
结束
P(4)
4
因为w＝0不满足语句1，所以直接跳到语句5、6，从而p(0)执行完毕，p(0)要进行“出栈”操作。
12．此时执行的语句有：4
5
P(1)
1
4
P(2)
2
4
P(3)
3
结束
P(4)
4
由于p(0)执行完成，且p(0)的方格a中为4，因此继续执行p(1)的语句4 ：p(w-1)；又由于p(1)方格c中w值为1，所以调用p(0)。
13．开始调用p(0)
5
P(0)
0
5
P(1)
1
4
P(2)
2
4
P(3)
3
结束
P(4)
4
当p（0）执行完了，就会执行p(1)中的语句5（所以在方格a中，填“5”）。
因为w＝0不满足语句1，所以直接跳到语句5、6，从而p(0)执行完毕，p(0)要进行“出栈”操作。
14．此时执行的语句有：5
5
P(1)
1
4
P(2)
2
4
P(3)
3
结束
P(4)
4
由于p(0)执行完成，且p(0)的方格a中为5，因此继续执行p(1)的语句5 （最后一句），所以p(1)执行完毕，p(1)要进行“出栈”操作。
15．
4
P(2)
2
4
P(3)
3
结束
P(4)
4
由于p(1)执行完成，且p(1)的方格a中为5，因此继续执行p(2)的语句5 （最后一句），所以p(2)执行完毕，p(2)要进行“出栈”操作。
注意：其实步骤10～15重复了步骤4～9,因为它们都调用的P(1)
16．
4
P(3)
3
结束
P(4)
4
由于p(2)执行完成，且p(2)的方格a中为4，因此继续执行p(3)的语句4 ：p(w-1)； 又由于p(3)方格c中w值为3，所以调用p(2)。
17．开始调用P(2)，此时执行的语句有：1、2、3
5
P(2)
2
4
P(3)
3
结束
P(4)
4
当p（2）执行完了，就会执行p(3)中的语句5（所以在方格a中，填“5”）。
执行p(2)的语句2：cout
同上面的情况相同，当执行到语句3，还要调用p(1)，只有p(1)执行完了，才能继续执行p(2)。
18．开始调用p(1)
省略……
注意：其实步骤17～29重复了3～15,因为它们都调用的P(2)
在这步骤中，又打印了2 1 1（见步骤3、4、10）
四．结论与分析：
步骤
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
结果
4
3
2
1
1
2
1
1
3
2
1
1
2
1
1
第5个结果重复第4个结果，这是因为他们都调用了p(1)
第6、7、8个结果重复第3、4、5个结果，这是因为他们都调用了p(2)
第9～15个结果重复第2～8个结果，这是因为他们都调用了p(3)
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
AI Hentai Generator
Generate AI Hentai for free.
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
C++ object layout is aligned with memory to optimize memory usage efficiency
Jun 05, 2024 pm 01:02 PM
C++ object layout and memory alignment optimize memory usage efficiency: Object layout: data members are stored in the order of declaration, optimizing space utilization. Memory alignment: Data is aligned in memory to improve access speed. The alignas keyword specifies custom alignment, such as a 64-byte aligned CacheLine structure, to improve cache line access efficiency.
Improved detection algorithm: for target detection in high-resolution optical remote sensing images
Jun 06, 2024 pm 12:33 PM
01 Outlook Summary Currently, it is difficult to achieve an appropriate balance between detection efficiency and detection results. We have developed an enhanced YOLOv5 algorithm for target detection in high-resolution optical remote sensing images, using multi-layer feature pyramids, multi-detection head strategies and hybrid attention modules to improve the effect of the target detection network in optical remote sensing images. According to the SIMD data set, the mAP of the new algorithm is 2.2% better than YOLOv5 and 8.48% better than YOLOX, achieving a better balance between detection results and speed. 02 Background & Motivation With the rapid development of remote sensing technology, high-resolution optical remote sensing images have been used to describe many objects on the earth’s surface, including aircraft, cars, buildings, etc. Object detection in the interpretation of remote sensing images
How to implement the Strategy Design Pattern in C++?
Jun 06, 2024 pm 04:16 PM
The steps to implement the strategy pattern in C++ are as follows: define the strategy interface and declare the methods that need to be executed. Create specific strategy classes, implement the interface respectively and provide different algorithms. Use a context class to hold a reference to a concrete strategy class and perform operations through it.
Similarities and Differences between Golang and C++
Jun 05, 2024 pm 06:12 PM
Golang and C++ are garbage collected and manual memory management programming languages respectively, with different syntax and type systems. Golang implements concurrent programming through Goroutine, and C++ implements it through threads. Golang memory management is simple, and C++ has stronger performance. In practical cases, Golang code is simpler and C++ has obvious performance advantages.
What are the underlying implementation principles of C++ smart pointers?
Jun 05, 2024 pm 01:17 PM
C++ smart pointers implement automatic memory management through pointer counting, destructors, and virtual function tables. The pointer count keeps track of the number of references, and when the number of references drops to 0, the destructor releases the original pointer. Virtual function tables enable polymorphism, allowing specific behaviors to be implemented for different types of smart pointers.
How to implement nested exception handling in C++?
Jun 05, 2024 pm 09:15 PM
Nested exception handling is implemented in C++ through nested try-catch blocks, allowing new exceptions to be raised within the exception handler. The nested try-catch steps are as follows: 1. The outer try-catch block handles all exceptions, including those thrown by the inner exception handler. 2. The inner try-catch block handles specific types of exceptions, and if an out-of-scope exception occurs, control is given to the external exception handler.
Groundbreaking CVM algorithm solves more than 40 years of counting problems! Computer scientist flips coin to figure out unique word for 'Hamlet'
Jun 07, 2024 pm 03:44 PM
Counting sounds simple, but in practice it is very difficult. Imagine you are transported to a pristine rainforest to conduct a wildlife census. Whenever you see an animal, take a photo. Digital cameras only record the total number of animals tracked, but you are interested in the number of unique animals, but there is no statistics. So what's the best way to access this unique animal population? At this point, you must be saying, start counting now and finally compare each new species from the photo to the list. However, this common counting method is sometimes not suitable for information amounts up to billions of entries. Computer scientists from the Indian Statistical Institute, UNL, and the National University of Singapore have proposed a new algorithm - CVM. It can approximate the calculation of different items in a long list.
How to iterate over a C++ STL container?
Jun 05, 2024 pm 06:29 PM
To iterate over an STL container, you can use the container's begin() and end() functions to get the iterator range: Vector: Use a for loop to iterate over the iterator range. Linked list: Use the next() member function to traverse the elements of the linked list. Mapping: Get the key-value iterator and use a for loop to traverse it.
