源代码通俗解释 源代码的概念 收藏 0

“通俗易懂的文字”+“经典案例”让你顺利入门“递归算法”

(大佬请绕行，比较基础!)递归是非常常见的一种算法，非常经典，可以解决非常多的问题。但我估计虽然大部分人知道递归，也能看得懂递归，但在实际运用中，很容易被递归给搞晕（数据，变量，函数等来回的出栈入栈）。今天写篇文章分享下，或许，能够给你带来一些帮助。

递归是一种解决问题的方法，将问题分解成规模更小的问题，不断地调用自身，解决小问题，直至问题不可再分，递归一般都是从结束条件一步一步往回计算

1. 递归必须有一个可以结束的条件，不然会陷入无限递归的噩梦中。而且，我们必须能根据当前参数的值，能够直接知道函数的返回结果是什么
2. 递归算法必须能改变状态向基本结束条件演进（必须能够有个最小规模的情况最为结束条件）
3. 递归算法必须调用自身

当一个函数被调用的时候，系统会把调用时的现场数据押入到系统调用栈（某段内存空间）

• 现场数据就是指函数变量名，函数所包含的参数，局部变量等
• 每次调用，压入栈的现场数据称为栈帧
• 当函数返回时，从调用栈的栈顶取得返回地址，恢复现场，弹出栈桢，按内存地址返回

一般来讲，系统调用栈容量有限，当递归的层数太多，超过递归最大层数，会报错，目前python支持最高1000层的调用

查看python的最大递归层数

其实递归的理解从语言上讲，基本上就这么多。下面开始分析一些代码实现

该数列由0和1开始，后面的每一项数字都是前面两项数字的和，数列的规律呈现为这个样子：[0,1,1,2,3,5,8,13,21···]，我们根据上述的递归三大定律分析来看：

1. 首先确认递归结束的条件，那么就是0，1，2这三个值，是定死的值
2. 对于大于2的索引值，有如下规律，f(n) = f(n – 1) + f(n – 2)，于是就可以构造如下递归函数求得计算结果
3. 因为要保存每一次的计算结果，最后累加，所以要有return值，将每一次递归的结果记录

代码实现如下

将十进制数转换为2/8/16进制的字符串形式

1. 递归的结束条件为：当前数值小于要转换的进制大小了
2. 比如说转换为2进制，那么就始终除以2取余数，那么就可以利用递归的算法拿到每次的结果，将问题规模一次次的减小

代码如下

要做这么个事情：“abcdefg” ->“gfedcba”（当然有很多方法，这里主要讲递归实现）

1. 递归结束条件为：原字符串只剩下最后一个的时候，这时候就不需要反转了
2. 每次收集当前字符串的s[0]的字符作为反转，减小问题规模

代码如下

本文主要分享了递归相关的概念和理解，并提供了几个最最基础的利用递归思想解决问题的代码(可能你会觉得本篇中的代码很简单，主要是不想给刚接触递归的那些人弄昏)，下一篇会分享几个稍微复杂一点点的案例(但整体还是递归问题中比较简单的那种)。我觉得，最开始接触递归，懵逼是正常的，只有不断的练习，不断的思考，才有可能用好这种牛逼的方法。

我是一名奋战在编程界的pythoner，工作中既要和数据打交道，也要和erp系统，web网站保持友好的沟通……时不时的会分享一些提高效率的编程小技巧，在实际应用中遇到的问题以及解决方案，或者源码的阅读等等，欢迎大家一起来讨论！如果觉得写得还不错，欢迎关注点赞，谢谢。

怎么通俗的理解Netty呢？

目录

有了Netty，你可以实现自己的HTTP服务器，FTP服务器，UDP服务器，RPC服务器，WebSocket服务器，Redis的Proxy服务器，MySQL的Proxy服务器等等。

如果你想知道Nginx是怎么写出来的，如果你想知道Tomcat和Jetty是如何实现的，如果你也想实现一个简单的Redis服务器，那都应该好好理解一下Netty，它们高性能的原理都是类似的。

看一下传统的HTTP服务器的原理：

1. 创建一个ServerSocket，监听并绑定一个端口
2. 一系列客户端来请求这个端口
3. 服务器使用Accept，获得一个来自客户端的Socket连接对象
4. 启动一个新线程处理连接
1. 读Socket，得到字节流
2. 解码协议，得到Http请求对象
3. 处理Http请求，得到一个结果，封装成一个HttpResponse对象
4. 编码协议，将结果序列化字节流
5. 写Socket，将字节流发给客户端
5. 继续循环步骤3

HTTP服务器之所以称为 HTTP 服务器，是因为编码解码协议是HTTP协议，如果协议是Redis协议，那它就成了Redis服务器，如果协议是WebSocket，那它就成了WebSocket服务器，等等。

使用Netty你就可以定制编解码协议，实现自己的特定协议的服务器。

上面我们说的是一个传统的多线程服务器，这个也是Apache处理请求的模式。在高并发环境下，线程数量可能会创建太多，操作系统的任务调度压力大，系统负载也会比较高。那怎么办呢？

于是 NIO 诞生了，NIO并不是Java独有的概念，NIO代表的一个词汇叫着IO多路复用。它是由操作系统提供的系统调用，早期这个操作系统调用的名字是 select ，但是性能低下，后来渐渐演化成了Linux下的epoll和Mac里的kqueue。我们一般就说是epoll，因为没有人拿苹果电脑作为服务器使用对外提供服务。而Netty就是基于Java NIO技术封装的一套框架。为什么要封装，因为原生的Java NIO使用起来没那么方便，而且还有臭名昭著的bug，Netty把它封装之后，提供了一个易于操作的使用模式和接口，用户使用起来也就便捷多了。

那NIO究竟是什么东西呢？

NIO的全称是NoneBlocking IO，非阻塞IO，区别与BIO，BIO的全称是Blocking IO，阻塞IO。那这个阻塞是什么意思呢？

1. Accept是阻塞的，只有新连接来了，Accept才会返回，主线程才能继
2. Read是阻塞的，只有请求消息来了，Read才能返回，子线程才能继续处理
3. Write是阻塞的，只有客户端把消息收了，Write才能返回，子线程才能继续读取下一个请求

所以传统的多线程服务器是BlockingIO模式的，从头到尾所有的线程都是阻塞的。这些线程就干等在哪里，占用了操作系统的调度资源，什么事也不干，是浪费。

那么NIO是怎么做到非阻塞的呢？

它用的是 事件机制 。它可以用一个线程把Accept，读写操作，请求处理的逻辑全干了。如果什么事都没得做，它也不会死循环，它会将线程休眠起来，直到下一个事件来了再继续干活，这样的一个线程称之为NIO线程。

Netty是建立在NIO基础之上，Netty在NIO之上又提供了更高层次的抽象。

在Netty里面，Accept连接可以使用单独的线程池去处理，读写操作又是另外的线程池来处理。

Accept连接和读写操作也可以使用同一个线程池来进行处理。而请求处理逻辑既可以使用单独的线程池进行处理，也可以跟放在读写线程一块处理。线程池中的每一个线程都是NIO线程。用户可以根据实际情况进行组装，构造出满足系统需求的并发模型。

Netty提供了内置的常用编解码器，包括行编解码器［一行一个请求］，前缀长度编解码器［前N个字节定义请求的字节长度］，可重放解码器［记录半包消息的状态］，HTTP编解码器，WebSocket消息编解码器等等

Netty提供了一些列生命周期回调接口，当一个完整的请求到达时，当一个连接关闭时，当一个连接建立时，用户都会收到回调事件，然后进行逻辑处理。

Netty可以同时管理多个端口，可以使用NIO客户端模型，这些对于RPC服务是很有必要的。

Netty除了可以处理TCP Socket之外，还可以处理UDP Socket。

在消息读写过程中，需要大量使用ByteBuffer，Netty对ByteBuffer在性能和使用的便捷性上都进行了优化和抽象。

本质：

1）JBoss做的一个Jar包。

2）目的：快速开发高性能、高可靠性的网络服务器和客户端程序。

3）优点：提供异步的、事件驱动的网络应用程序框架和工具。

这里 EchoServerHandler 是其业务逻辑的实现者，大致代码如下：

看看 EchoServerHandler 的代码，其中的参数： public void messageReceived(ChannelHandlerContext ctx, MessageEvent e) ，MessageEvent就是一个事件。这个事件携带了一些信息，例如这里 e.getMessage() 就是消息的内容，而 EchoServerHandler 则描述了处理这种事件的方式。一旦某个事件触发，相应的Handler则会被调用，并进行处理。这种事件机制在UI编程里广泛应用，而Netty则将其应用到了网络编程领域。

在Netty里，所有事件都来自 ChannelEvent 接口，这些事件涵盖监听端口、建立连接、读写数据等网络通讯的各个阶段。而事件的处理者就是 ChannelHandler ，这样，不但是业务逻辑，连网络通讯流程中底层的处理，都可以通过实现 ChannelHandler 来完成了。事实上，Netty内部的连接处理、协议编解码、超时等机制，都是通过handler完成的。

下图描述了Netty进行事件处理的流程。 Channel 是连接的通道，是ChannelEvent的产生者，而 ChannelPipeline 可以理解为ChannelHandler的集合。

除了之前说到的事件驱动机制之外，Netty的核心功能还包括两部分：

• Zero-Copy-Capable Rich Byte Buffer零拷贝的Buffer。为什么叫零拷贝？因为在数据传输时，最终处理的数据会需要对单个传输层的报文，进行组合或者拆分。NIO原生的ByteBuffer无法做到这件事，而Netty通过提供Composite(组合)和Slice(切分)两种Buffer来实现零拷贝。这部分代码在 org.jboss.netty.buffer 包中。这里需要额外注意，不要和操作系统级别的Zero-Copy混淆了, 操作系统中的零拷贝主要是用户空间和内核空间之间的数据拷贝, NIO中通过DirectBuffer做了实现.
• Universal Communication API统一的通讯API。这个是针对Java的Old I/O和New I/O，使用了不同的API而言。Netty则提供了统一的API( org.jboss.netty.channel.Channel )来封装这两种I/O模型。这部分代码在 org.jboss.netty.channel 包中。

此外，Protocol Support功能通过handler机制实现。

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com