算法|算法--递归算法|算法

目录
一、递归算法基本概念
1.什么是递归?
2.递归栈
3.递归算法分析
二、递归三步曲
三、例题解析
1.斐波那契数列斐波拉契数列

2.反转链表:反转链表
3.链表求和链表求和
总结
前言
本文是笔者第一次写类似的文章，旨在分享自己学习时的感悟，并用做学习的笔记。篇幅较长，但相信能给读者带来收获,如有不足欢迎指点。

一、递归算法基本概念 1.什么是递归?
自己调用自己的算法称为递归算法，这就好比套娃，大的套娃里面还有一个与它相似的套娃，如此反复直到套娃大小达到足够小。
和套娃类似的递归算法，有两个基本条件:
1.结束条件(套娃达到足够小后就没有在下一个套娃了)
2.状态转换方程:调用本身(除最小套娃外，每个套娃下都有比他小一级的套娃)

文章图片

(图片来源与百度）

2.递归栈
递归的实现是基于栈的数据结构,有先进后出的特点
3.递归算法分析
对于递归算法的分析通常将递归算法构成递归树，进一步分析，由于本文主要讲解递归代码的编写，这里不展开讲解，感兴趣的读者可以自行查阅相关材料。

二、递归三步曲绝大多数人在写递归算法时，会比较茫然无从下手，相信按下面的步骤会对编写递归算法有较大的帮助。
1.明确函数意义:即你写的这个函数目的是什么，有什么作用，返回值是什么。
这个难度不大，不因为大部分时候我们都是明确了函数的作用再来编写函数的。但这并不意味着，它不重要，相反准确无误的函数意义对后续代码编写能起到大的帮助。
2.结束条件:即何时停止递归，若结束条件填写不当，容易出现无限递归的情况。结束条件的选择，需要根据实际情况来选择。
3.递归方程:即函数如何调用本身,先用数学语言(或自己的语言)表示出来。这是递归函数的关键。
此外为了代码的健壮性还需考虑输入错误的情况。
当然光说上面的步骤太抽象，下面通过上述步骤来分析几道例题，先试着自己解题在看解析效果会更好哦!
三、例题解析 1.斐波那契数列斐波拉契数列

文章图片

示例:

输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1

输入：3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2

输入：4 输出：3 解释：F(4) = F(3) + F(2) =2 + 1 = 3

本题的最优解并不是递归方法,但由于本问简介的是递归算法，为此下面通过递归算法来解决该题:

/*
本题的三个步骤，题设都有明确给出:
1.函数意义:求解F(n)int n>=0错误输入 n<0
2.结束条件:
n=0 || n=1
3.递归方程:
F(n)=n; n=0 || n=1
F(n)=F(n-1)+F(n-2); n>1
*/

下面给出java代码:

class Solution { //递归写法 public int fib(int n) { /* 1.函数意义:求解F(n) 2.结束条件: n=0 || n=1 3.递归方程: fib(n)=n; n=0 || n=1 fib(n)=fib(n-1)+fib(n-2); n>1 */ if(n<0) return -1; //输入不符合条件 if(n==0 || n==1) return n; return fib(n-1)+fib(n-2); } }

本题题设给出了函数的数学表达式，较为简单，但大部分题目不会明显的给出式子，需要自己挖掘。
2.反转链表:反转链表

文章图片

同样的本题的最优解法也不是递归，但仍然只讲解递归的方法

/*
单链表本身就具有很强的递归性
思路:
对于一个较长的单链表,如 1->2->3->4->5
我们可以记2->3->4->5 为链表l
则原链表为: 1->l,
那么反转链表应该分为下面三步:
(1)反转 l 得到 l' 且反转后的头节点记为newhead，显然尾节点为2(head.next);
newhead=reverseList(head.next);
(2) l'连接上 1即 2->1
head.next.next=head; //head.next=22.next=head
(3)断开1与原链表的连线1->2
head.next=null;
思考: 上述(1)(2)(3)的顺序能否互换,答案是不能。
原因:
步骤(1)中的l是原链表中第二个节点以及后续的节点，那么首先 2必须连着3,即2->3 不能断，若执行了步骤(2) 2->1 因为单链表的节点都比较专一，不会同时连着两个节点，显然2->3就断开了，所以必须是先(1)在(2)
至于(2)(3)的顺序若不采用而外指针做记录，那么显然
head.next.next=head;
head.next=null;
的顺序是定死的所以给先(2)在(3)
综上顺序不能互换
1.函数意义:
根据题意,本题的目的是反转链表,函数的输入参数的链表的头元素，返回参数是反转后的头元素
2.结束条件:
思路中的伪代码存在head.next,为此head不能为null,而对于单节点的链表，其显然是不用反转的
(1)head==nullreturn head;
(2)head.next==null:单节点不用反转return head;
3.递归函数:
reverseList(head)=head; head==null || head.next==null;
reverseList(head)={
newhead=reverseList(head.next);
head.next.next=head;
head.next=null;
return newhead;
}

*/

下面给出java代码

class Solution { public ListNode reverseList(ListNode head) { if(head==null || head.next==null) return head; ListNode newhead=reverseList(head.next); //反转头结点的下一个节点开始到尾节点的链表 head.next.next=head; //反转后的新链表连接头节点 head.next=null; //断开原有的连接 return newhead; } }

3.链表求和链表求和

文章图片

思路:
先来看下我们正常计算时的方法:

文章图片

可以看出其实是反复的进行 c1+c2+cn 且逢10进1的操作,其中c1，c2表示两个数的同位数的相同位置的单位数，cn表示低位的进位数，起始cn=0
所以大体解题思路如下:
(1)两个头结点之和与cn相加，记作valval=l1.val+l2.val+cn;
(2)取val%10作为头节点head的值head.val=val%10;
(3)取val/10作为新的进位符，对后续节点求和，求和结果作为head的后续链表;
head.next=addTwoNums(l1.next,l2.next,val/10);
1.函数意义:
进位为cn的情况下对l1,l2做求和操作
参数: ListNode l1, ListNode l2, int cn
返回值:求和后的头结点
2.结束条件:
(1)l1==null && l2==null
cn=0return null;
cn!=0 return new ListNode(cn);

细心的读者可能有看出我上面给的例子和题设的例子不同，主要是想表达l1与l2长度可能不同，所以可能会有一个已经为null，而另外一个不是null的情况
(2)两个有且只有一个为null
cn=0:return 不为空的链表
cn!=0:还需要对不为null的链表做与cn相加的操作，这里记这个操作为addcn，后面还会给出这个函数的具体实现，读者可以先将这个函数当成已经封装好的了，其功能为实现链表与某个数相加。
3.递归函数:
addTwoNums(l1,l2,cn) = (cn==0?l1:new ListNode(cn)); l1==null && l2==null
addTwoNums(l1,l2,cn) ={
ListNode head=l1==null?l2:l1; //取不为空的链表
return cn==0?head:addcn(head,cn); //cn为0就直接返回非空链表，否则还要求和
}
addTwoNums(l1,l2,cn) ={
int val=l1.val+l2.val+cn; //两个头结点之和与cn相加
ListNode head=new ListNode(val%10); //取val%10作为头节点head的值

//取val/10作为新的进位符，对后续节点求和，求和结果作为head的后续链表
head.next=addTwoNums(l1.next,l2.next,val/10);
return head;
}

下面给出java代码:

public ListNode addTwoNums(ListNode l1,ListNode l2,int cn){ if(l1==null && l2==null){ return cn==0?l1:new ListNode(cn); } if(l1==null || l2==null){ ListNode head=l1==null?l2:l1; return cn==0?head:addcn(head,cn); } int val=l1.val+l2.val+cn; //两个头结点之和与cn相加 ListNode head=new ListNode(val%10); //取val%10作为头节点head的值 head.next=addTwoNums(l1.next,l2.next,val/10); //取val/10作为新的进位符，对后续节点求和，求和结果作为head的后续链表 return head; }

上面的代码中涉及到另外一个函数，即addcn()：将链表加上某一个数

该函数可以通过递归，也可以通过迭代实现，下面讲解递归实现:
思路:
还是先上图:

文章图片

可以看出其实就是反复进行 c+cn 且逢10进1 ，当进位为0时停止操作
所以大体思路如下:
1.头节点与cn相加结果记作 val
val=head.val+cn
2.取val%10作为新头节点的值
newhead.val=val%10;
3.取val/10作为新进位数，与head.next及其后续节点相加,结果为newhead.next
newhead.next=addcn(head.next,val/10);
1.函数意义: 链表代表的数+cn
2.结束条件:
(1)cn==0 && head!=null:return head;
(2)cn==0 && head==null:return head;
合并(1)(2)-->
(1)cn==0:return head;
(2)cn!=0 && head==null:return new ListNode(cn);
3.递归方程:
addcn(head,cn)=head; cn==0
addcn(head,cn)=return new ListNode(cn); cn!=0 && head==null
addcn(head.cn)={
val=head.val+cn;
newhead.val=val%10;
cn=val/10;
newhead.next=addcn(head.next,cn)
}

public ListNode addcn(ListNode head,int cn){ if(cn==0) return head; if(head==null) return new ListNode(cn); int val=head.val+cn; ListNode newhead=new ListNode(val%10); newhead.next=addcn(head.next,val/10); return newhead; }

综上本题总代码如下:

class Solution { //递归public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return addTwoNums(l1,l2,0); }public ListNode addTwoNums(ListNode l1,ListNode l2,int cn){ if(l1==null && l2==null){ return cn==0?l1:new ListNode(cn); } if(l1==null || l2==null){ ListNode head=l1==null?l2:l1; return cn==0?head:addcn(head,cn); } int val=l1.val+l2.val+cn; //两个头结点之和与cn相加 ListNode head=new ListNode(val%10); //取val%10作为头节点head的值 head.next=addTwoNums(l1.next,l2.next,val/10); //取val/10作为新的进位符，对后续节点求和，求和结果作为head的后续链表 return head; } public ListNode addcn(ListNode head,int cn){ if(cn==0) return head; if(head==null) return new ListNode(cn); int val=head.val+cn; ListNode newhead=new ListNode(val%10); newhead.next=addcn(head.next,val/10); return newhead; } }

其实对一个链表为空，另外一个链表不为空的情况，也可以把为空的链表看出n个0组成的链表（n为非空链表的长度)
由于篇幅原因这里不做讲解，只给出代码：

class Solution { //法二:递归 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return addTwoNum(l1,l2,0); } public ListNode addTwoNum(ListNode l1,ListNode l2,int cn){ if(l1==null && l2==null && cn==0) return null; int v=(l1!=null?l1.val:0)+(l2!=null?l2.val:0)+cn; int val=v%10; int c=v/10; ListNode head=new ListNode(val); head.next=addTwoNum(l1!=null?l1.next:null,l2!=null?l2.next:null,c); return head; } }

除了上述讲解的问题外，还有很多递归算法的题目，读者可以自行上查找练习，下面给出几个推荐的题目:
1.汉诺塔问题2.最长同值路径3.合并两个排序的链表
下期预告(说不定是年更嘿嘿):
算法--递归应用：笔者认为分治，深度优先搜索，回溯算法是递归的应用为此放在递归应用中进行讲解

总结本片给出了递归的概念、递归的三部曲并通过详解三个例子来具体讲解递归三部曲。

【算法|算法--递归】