🎥 个人主页：Dikz12🔥个人专栏：算法(Java)📕格言：吾愚多不敏，而愿加学欢迎大家👍点赞✍评论⭐收藏 

目录

1. 递归概述

2.汉诺塔问题 

 题目描述​编辑

题解 

代码实现       

3.合并两个有序链表

题目描述 

题解 

代码实现 

4.反转链表

题目描述 

题解 

​编辑 代码实现

 5.Pow(x, n)

题目描述 

题解 

代码实现 

1. 递归概述

  1. 什么是递归？

简单来说，就是函数自己调用自己的情况.

  2. 为什么用递归？

 本质上：主问题 --> 相同的子问题；  子问题 --> 相同的子问题.

3. 如何理解递归？ 

 1.递归展开的细节图.（不用有强迫症，每道题都展开，就得不偿失了）

 2. 二叉树的题目.

 3.宏观看待递归的过程

不要在意递归的展开图把递归当作一个黑盒相信这个黑盒一定能完成这歌任务.

4.如何写好一个递归？ 

 1.先找到相同的子问题！ ---> 函数头的设计

 2. 只关心某一个子问题是如何解决的. ----> 函数体书写

 3. 注意一下递归函数的出口即可. 

2.汉诺塔问题 

 题目描述

题解 

可以被解释为：

1

.

对于规模为 n 的问题，我们需要将 A 柱上的 n 个盘⼦移动到C柱上。

2.

规模为 n 的问题可以被拆分为规模为 n-1 的⼦问题：

将 A 柱上的上⾯ n-1 个盘⼦移动到B柱上。 将 A 柱上的最⼤盘⼦移动到 C 柱上，然后将 B 柱上的 n-1 个盘⼦移动到C柱上。

当问题的规模变为 n=1 时，即只有⼀个盘⼦时，我们可以直接将其从 A 柱移动到 C 柱。

 综上从宏观的角度分析：

1. 重复的子问题。(函数头)

       将A柱子上的盘子，借助B柱子，转移到C柱子上.

 2.只关心某一个子问题在做什么。(函数体)

    3. 递归出口.  -->   N == 1

 分析完之后，代码其实已经写完了。

代码实现       

<code> public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {

dfs( A, B, C, A.size());

}

public void dfs(List<Integer> A, List<Integer> B, List<Integer> C,int n) {

if(n == 1) {

C.add(A.remove(A.size() - 1));

return;

}

dfs(A, C, B ,n - 1);

C.add(A.remove(A.size() - 1));

dfs(B, A, C, n - 1);

}

3.合并两个有序链表

题目描述 

题解 

递归函数的含义：交给你两个链表的头结点，你帮我把它们合并起来，并且返回合并后的头结点；  函数体：选择两个头结点中较⼩的结点作为最终合并后的头结点，然后将剩下的链表交给递归函数去处理； 递归出⼝：当某⼀个链表为空的时候，返回另外⼀个链表。

代码实现 

<code> public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

if(l1 == null) {

return l2;

}

if(l2 == null) {

return l1;

}

if(l1.val <= l2.val) {

l1.next = mergeTwoLists(l1.next,l2);

//作为新的头结点

return l1;

}else{

l2.next = mergeTwoLists(l1,l2.next);

return l2;

}

}

4.反转链表

题目描述 

题解 

 递归函数的含义：交给你⼀个链表的头指针，你帮我逆序之后，返回逆序后的头结点； 函数体：先把当前结点之后的链表逆序，逆序完之后，把当前结点添加到逆序后的链表后⾯即可； 递归出⼝：当前结点为空或者当前只有⼀个结点的时候，不⽤逆序，直接返回。

 代码实现

<code> 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;

}

 5.Pow(x, n)

题目描述 

题解 

递归函数的含义：求出 x 的 n 次⽅是多少，然后返回； 函数体：先求出 x 的 n / 2 次⽅是多少，然后根据 n 的奇偶，得出 x 的 n 次⽅是多少； 递归出⼝：当 n 为 0 的时候，返回 1 即可。

细节问题：

  2.   -2 ^31 其中2^31就会发生越界，int 改成long类型. 

代码实现 

<code> public double myPow(double x, long n) {

return n < 0 ? 1 / pow(x,-n) : pow(x,n);

}

public double pow(double x,long n) {

if(n == 0) {

return 1;

}

double tmp = myPow(x,n / 2);

return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;

}