黑马程序员技术交流社区

标题: 递归就是高中数学的归纳法~~ [打印本页]

---

作者: sandra_bae    时间: 2015-5-2 20:12
标题: 递归就是高中数学的归纳法~~
递归和数学归纳法                 

计算机就是数学的一个分支，不管你认不认同，你都会发现在编程的过程中，你能够发现很多的数学思维的闪现，就比如递归，递归可以让程序简化，与非递归比较，简单的递归函数省去了大段大段的代码，让人叹服不已，递归往往能体现设计者头脑的聪慧，但是递归的思想与数学又有什么相关呢？
本文将介绍递归与数学归纳法之间的联系，希望给读者一些启迪。
要说递归得先说，数学归纳法，想必每一个程序员在高中的时候就应该学习了数学归纳法，当我们需要去证明一个证明题时，很可能就要用到数学归纳法，数学归纳法的思想如下：
一般地，证明一个与自然数n有关的命题P(n），有如下步骤：
（1）证明当n取第一个值n0时命题成立。n0对于一般数列取值为0或1，但也有特殊情况；
（2）假设当n=k（k≥n0，k为自然数）时命题成立，证明当n=k+1时命题也成立。
综合（1）（2），对一切自然数n（≥n0），命题P(n）都成立。

其实，数学归纳法利用的是递推的原理，形象地可以叫做多米诺原理。因为N+1的成立就可以向前向后递推所有数都成立。

    而递归利用的也是递推的原理，在整个程序中，反复实现的将是同一个原理。在这一点上，递归与数学归纳法本质是相同的。所以往往可以利用数学归纳法来设计递归的实现。计算机是数学应用的一个分支在这里体现的淋漓尽致。

这里我们先来看一个例子，非常简单，设计一程序，求自然数N的阶乘N！：

现在已知N!=N*(N-1)*(N-2)*(N-3)*…*2*1

    首先可知当N=1时 N!=1

    第二步可设当R(N)=N!，R(N+1)=(N+1)!

    第三步，求R(N+1)与R(N)之间的关系。R(N)=N!，
    而R(N+1)=(N+1)!=(N+1)*(N)*(N-1)*…*2*1=(N+1)*N!=(N+1)*R(N)
    即：R(N+1)=(N+1)*R(N) =〉 R(N)=N*R(N-1)

    现在根据这个公式草略地构造一个函数：
    factorial (int N)
    {
       return N * factorial (N - 1)   /*    递归部分    */
    }

    接下来补充截止部分，这一部分在整个过程中只使用一次，没有它，程序就将无限递归下去。可以说它是程序运行栈的栈顶，到了它，就开始一步步退栈了。
    函数改为：

    factorial (int N)
    {
       if (N == 1)   return 1;
       return N * factorial (N - 1)   /*    递归部分    */
    }


  上面的步骤是可以颠倒的，而且首先设计截至部分还要好一些。

    现在来总结设计递归程序的步骤：
    一、用数学归纳法分析问题，根据数学归纳法的第一步得出截至部分。

    二、根据数学归纳法的第三步来构造函数的递归部分。其实这个求解过程就是找出R(N)与R(N-1)的关系式。

    现在利用总结出的方法做一个练习，比较经典的汉诺塔。

    汉诺塔想必大家都知道：三个立柱（命名为from、temp、to，from为圆盘初始所在立柱、to是目标立柱），N个直径不相等的圆盘，将圆盘从from上一个一个移动在to上，要求，每次只能移动一个圆盘，而且只能在三个立柱之间移动。不能出现大盘压小盘的情况。

    首先用数学归纳法分析：
   当只有一个圆盘的时候，我们可以确定唯一动作：直接将圆盘从from移动到to上。

    现在假设有N个圆盘在from上，而我们可以将这些圆盘最终按要求移动到to上（当然也可以移动到temp上）。

    那么我们可以证明如果有N+1个时候，我们也可以将圆盘全部按要求移动到to上：因为我们可以先将上面的N个移动到temp上（第二步已假设），再把剩下的最后一个移动到to上，再把temp上的移动到to上。

    按照我们总结过的递归函数设计步骤来设计程序：
    首先，确定截至部分：当只有一个圆盘移动的时候，直接将它移动到to上。即：if (n == 1) move (n,  from, to);
    （这里的move函数意义是将n号圆盘，或者说初始状态下从上面数第n个圆盘，从from移动到to）

     第二步确定递归部分，其实就是N+1与N的关系部分，就是红色字体部分。现在开始把文字转化为程序：

    设Hanoi (int n, int from, int temp, int to)函数就是我们要求的汉诺塔实现函数，意义是将按直径递增摞在一起的n个圆盘从from按要求移动到to上，temp为辅助圆盘。

    可写出代码：
    Hanoi (n-1, from, temp);   /* 先将上面的N个移动到temp上 */
    move (n, from, to);   /* 剩下的最后一个移动到to上 */
    Hanoi (n-1, temp, to);   /* 再把temp上的移动到to上 */

    第二步完成，最后合成函数：
    void
    Hanoi (int n, int from, int temp, int to)
    {
       if (n == 1)
          move (n, from, to);
       else
       {
          Hanoi (n-1, from, temp);
          move (n, from, to);
          Hanoi (n-1, temp, to);
       }
    }

下面我们来看下一次例子，链表逆置。
假如链表只有一个元素，必然可以逆置
1->null ---------null<-1
假如链表有k个元素，也可以逆置，逆置后返回逆置后的头结点
那么只要证明链表有k+1个元素也可以逆置，新添加的元素在链表头。

其实代码很简单：
Node* reverse(Node* head)
{
　　Node* p;
//当链表只有一个元素的时候直接，直接返回，即逆置成功。
　　if( head->next ==null)   
　　{
　　　　return head;
　　}
　　else
　　{　　
//假设k个节点的链表可以逆置成功，并返回逆置后的链表头结点
　　　　p = reverse(head->next);     
//判断第k+1个节点(第k+1个节点位于链表头)是否可以逆置？如何做呢，前提：我们知道k个结点逆置后的尾节点，同时还知道第k+1个结点，所以下面就是逆置第k+1个结点
　　　　head->next->next = head;   
　　　　head->next = null;
//因为要返回逆置后的头结点，所以将尾节点向上传递
　　　　return p;
　　}
}   
    使用数学归纳法设计递归程序最大的好处就是可以使设计者摆脱对递推的顾虑。因为你设计的代码必定隐含着递推的步骤。直接根据你的分析文字转化为代码即可。
   
    本文还有很多不足之处，欢迎读者指教。

---

作者: lshaizj    时间: 2015-5-2 20:21
学习ING，先赞一个

---

作者: lixunwen    时间: 2015-5-2 21:29
学习啦！逻辑思维特别强

---

作者: 我爱吃橙子    时间: 2015-5-3 00:51
先顶了，再慢慢看

---

作者: 浪死歌    时间: 2015-5-3 01:08
很有用呀~  

---

作者: 米江波    时间: 2015-5-3 10:37
还有学习到递归 不过楼主的精神可嘉 定一个

---

作者: sandra_bae    时间: 2015-5-3 10:50

米江波 发表于 2015-5-3 10:37
还有学习到递归 不过楼主的精神可嘉 定一个

其实学得也不好，只会做些简单的~~

---

作者: sandra_bae    时间: 2015-5-3 10:51

我爱吃橙子 发表于 2015-5-3 00:51
先顶了，再慢慢看

:)其实我也没认真看完，同学习了~

---

作者: sandra_bae    时间: 2015-5-3 10:52

longsee88 发表于 2015-5-3 00:14
这也有？赶紧mark一下，明天好好看看

:):):)加油~

---

作者: brouse    时间: 2015-5-3 10:52
可以写的简明些

---

作者: 和鹏    时间: 2015-5-3 10:55
谁教你的递归就是数学归纳法？

---

作者: sandra_bae    时间: 2015-5-3 11:08

和鹏 发表于 2015-5-3 10:55
谁教你的递归就是数学归纳法？

原理不是一样的吗？
刚研究一天，请赐教~~:)

---

作者: sunyue    时间: 2015-5-3 17:53
研究的好透彻啊

---

作者: 哔哩哔哩    时间: 2015-5-3 21:24
太多了，看不下去。。不是太懂，但是递归会用

---

作者: sandra_bae    时间: 2015-5-3 21:57

哔哩哔哩 发表于 2015-5-3 21:24
太多了，看不下去。。不是太懂，但是递归会用

嗯嗯，我只会做一些简单的应用。

---

作者: lwl    时间: 2015-5-3 22:12
赞一个               

---

作者: Cat    时间: 2015-5-4 08:40
赞一个~

---

作者: 铃铃铃铃铃锋    时间: 2015-5-4 18:31
说的好详细。   学习了

---

作者: 和鹏    时间: 2015-5-10 22:48

sandra_bae 发表于 2015-5-3 11:08
原理不是一样的吗？
刚研究一天，请赐教~~:)

递归是从终点跑到起点再拿着那个结束递归的钥匙返回到终点。
数学归纳法是从起点一路向终点探索的过程。
这才是原理。

---

作者: shw16888    时间: 2015-5-10 22:49
赞一个！！！

---

作者: qian0217wei    时间: 2015-5-11 00:36
递归不难，关键在于寻求规律！

---

作者: fantacyleo    时间: 2015-5-11 14:35

和鹏 发表于 2015-5-10 22:48
递归是从终点跑到起点再拿着那个结束递归的钥匙返回到终点。
数学归纳法是从起点一路向终点探索的过程。
...

递归定义的原理就是数学归纳法，这在数学上有定论，google一下就明白。具体叙述可参考Terence Tao的《Analysis》第2章，中译本《陶哲轩实分析》。另外我觉得Carnegie Mellon大学的ML语言讲义里有一句话很经典：

when programming recursively, think inductively

起点终点不过是你人为的划分，而且你说的递归终点实际就是数学归纳法的起点。递归的终点跑到起点，和数学归纳法的起点到终点是一回事。如果非要执着于起点终点之分，把递归写成bottom-up就是了。比如1+2+...+100的bottom up写法：

1. public int getSum(int n, int end, int sum) {
   
2.     if (n > end)
   
3.          return sum;
   
4.     else
   
5.         getSum(n + 1, end, sum + n);
   
6. }

复制代码

---

作者: 和鹏    时间: 2015-5-11 16:53

fantacyleo 发表于 2015-5-11 14:35
递归定义的原理就是数学归纳法，这在数学上有定论，google一下就明白。具体叙述可参考Terence Tao的《Anal ...

谢谢指教。终点和起点是我的个人理解。我并不认为递归的终点就是数学归纳法的起点。只是想说明我目前理解的递归和归纳法既存在联系又有区别。对一种思想不同的时期有不同的理解，目前我的理解是这样的，随着时间的推移，对真理的追寻，会有一些更有深度的理解吧。还是很谢谢你的指点。

---

作者: Rdxer    时间: 2015-5-11 18:03
好复杂，，，，，，，，，，，，，，，，，，，，，，  

---

作者: YQliang    时间: 2015-5-11 18:19
这个内容深度确实大,

---

作者: ye646682485    时间: 2015-5-11 21:08
长知识了，不错

---

作者: LPStone    时间: 2015-5-11 21:09
说的好详细啊！！！！！

---

作者: 牛仔很忙fire    时间: 2015-5-11 21:13
学习了，赞一下

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2