算法讲解7：递归

递归：在数学与计算机中是指在函数的定义中只用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法

1.递归出口（边界条件）：找全递归终止条件

2.注意：写代码只考虑当前问题怎么解决，不分析下层问题怎么展开，不用去倒明白，就能处理当前就行

3.理解：画图，构思，找规律

4.例题：

题目描述

面试题 08.06. 汉诺塔问题

在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上（即每一个盘子只能放在更大的盘子上面）。移动圆盘时受到以下限制：
(1) 每次只能移动一个盘子；
(2) 盘子只能从柱子顶端滑出移到下一根柱子；
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。

示例 1：
输入：A = [2, 1, 0]，B = []，C = []
输出：C = [2, 1, 0]

第一步，先简化题意，就是把1柱的盘子移动到3柱，以2柱为媒介，归根到底，还是先放大盘子，但是1柱先动的是小盘子，所以通过媒介把小盘子放到下面，实现“让大盘子能比小盘子先动”,

第二步：那么这种题肯定无法用循环解决，我们用栈来充当柱子，再编写“根据不同请况盘子不同移动”的逻辑，我们需要一个函数，在调用的时候传入123三柱的栈，

那麽我们就知道一共需要做3个事情，设盘子数量aa，s起点，e终点，h媒介

1.把x-1个盘子通过媒介传到柱子，s->e->h

2.处理最后一个，s->e

3.把前面x-1个盘子移回正轨，h->s->e

代码

package 博客; import java.util.Stack; import java.util.Scanner; public class 递归 { public static void hannuota(int aa, Stack<Integer> s, Stack<Integer> e, Stack<Integer> h) //s起点，e终点，h媒介 { if(aa==1)//这是减到底了，写这个if的目的是里面可以放return { int p=s.pop(); e.add(p); return ; } hannuota(aa-1,s,h,e);//1，把aa-1个都处理，这一行就是只处理一次，处理完后调用自身，就是持续调用aa-1次 int d=s.pop();//2 处理最后一个，后面每一次都会运行这个，决定不同的是输入的值 e.add(d); hannuota(aa-1,h,e,s);//3 必须在最后，把前面的aa-1个放回正轨 } public static void main(String[] args) { Stack<Integer> a = new Stack<>(); Stack<Integer> b = new Stack<>(); Stack<Integer> c = new Stack<>(); Scanner sc=new Scanner(System.in); int n=sc.nextInt(); for(int i=0;i<n;i++) { a.add(sc.nextInt()); } int aa=a.size(); hannuota(aa,a,c,b); System.out.println(c.toString()); } }