当前位置:网站首页>1143_ SiCp learning notes_ Tree recursion
1143_ SiCp learning notes_ Tree recursion
2022-07-06 13:50:00 【grey_ csdn】
All learning summary :GitHub - GreyZhang/g_SICP: learn SICP and hack lisp.
A typical example of tree recursion is the solution of Fibonacci sequence , The above is a simple definition rule description . This description can be easily converted into a recursive function by code , The last screenshot of the above document is lisp How to implement .
If the replacement model is used for expansion , This is the solution process of Fibonacci sequence . It can be seen from here that , Half the work is actually repetitive . In fact, it can be analyzed from the characteristics of the code itself , Because every recursion calls the function twice .
This is an optimization of Fibonacci sequence solution , In fact, the optimization method is mainly aimed at the iterative part in the previous formula . In previous software design , The state saving and other work of these two parts are actually completely entrusted to the parser . And the improved way , Make a transition between the two maintenance states , In fact, the saving of some temporary information is not completely handled by the parser, but put into memory . The design of software is actually very easy to understand .
This is a test of the above software design . Equivalent functions can also be easily used python To do a writing test .
def fib(n):
if n <= 1:
return n
else:
return fib(n - 1) + fib(n - 2)
def fib_iter(a, b, n):
if n == 0:
return b
else:
return fib_iter(a + b, a, n - 1)
def new_fib(n):
return fib_iter(1, 0, n)
The computational effect of both languages is the same . I also compared the solution method with the first scheme , Solve in the computer fib(100) The process is very long . And the improved way , In fact, it has good execution efficiency , Whether it's lisp still python.
Here is another classic question : The combination of coins . The disassembly of this problem is divided into two steps , Described as the colored part above . About this description , In my own understanding, I should consider this : All the combination methods actually have 2 Kind of , One is that the first kind of coins are not used ; The other is the case of using at least one coin of the first kind . Then the case of using at least one coin of the first kind can be considered as the total amount minus the face value of one coin of the first kind , Any combination of the remaining amounts . such , It's easy to build the following recursive program .
such , Basically finished reading the content of tree recursion . Through the study of this chapter , I still see a useful way of thinking . however , The realization of many laws or methods is actually supported by certain data theory to a great extent . look , Mathematics is also a very important tool and method .
边栏推荐
- 为什么要使用Redis
- 5月14日杂谈
- [graduation season · advanced technology Er] goodbye, my student days
- 8. C language - bit operator and displacement operator
- Leetcode. 3. Longest substring without repeated characters - more than 100% solution
- MySQL事务及实现原理全面总结,再也不用担心面试
- . Net6: develop modern 3D industrial software based on WPF (2)
- C语言入门指南
- 2022泰迪杯数据挖掘挑战赛C题思路及赛后总结
- Analysis of penetration test learning and actual combat stage
猜你喜欢
Write a program to simulate the traffic lights in real life.
3. Number guessing game
8. C language - bit operator and displacement operator
[面试时]——我如何讲清楚TCP实现可靠传输的机制
记一次猫舍由外到内的渗透撞库操作提取-flag
A comprehensive summary of MySQL transactions and implementation principles, and no longer have to worry about interviews
甲、乙机之间采用方式 1 双向串行通信,具体要求如下: (1)甲机的 k1 按键可通过串行口控制乙机的 LEDI 点亮、LED2 灭,甲机的 k2 按键控制 乙机的 LED1
QT meta object qmetaobject indexofslot and other functions to obtain class methods attention
优先队列PriorityQueue (大根堆/小根堆/TopK问题)
4. Binary search
随机推荐
Difference and understanding between detected and non detected anomalies
MATLAB打开.m文件乱码解决办法
[dark horse morning post] Shanghai Municipal Bureau of supervision responded that Zhong Xue had a high fever and did not melt; Michael admitted that two batches of pure milk were unqualified; Wechat i
【九阳神功】2016复旦大学应用统计真题+解析
7-9 制作门牌号3.0(PTA程序设计)
[au cours de l'entrevue] - Comment expliquer le mécanisme de transmission fiable de TCP
This time, thoroughly understand the MySQL index
记一次猫舍由外到内的渗透撞库操作提取-flag
3.输入和输出函数(printf、scanf、getchar和putchar)
[面试时]——我如何讲清楚TCP实现可靠传输的机制
[the Nine Yang Manual] 2022 Fudan University Applied Statistics real problem + analysis
Have you encountered ABA problems? Let's talk about the following in detail, how to avoid ABA problems
【头歌educoder数据表中数据的插入、修改和删除】
The difference between overloading and rewriting
【九阳神功】2020复旦大学应用统计真题+解析
The difference between abstract classes and interfaces
Caching mechanism of leveldb
It's never too late to start. The tramp transformation programmer has an annual salary of more than 700000 yuan
4. Binary search
7-6 矩阵的局部极小值(PTA程序设计)