关于算法:记录一下自己学习递归的过程未完

6次阅读

共计 2160 个字符，预计需要花费 6 分钟才能阅读完成。

关注于把大问题合成为小问题，不要纠结于具体过程，齐全能够把递归函数看作一个魔法函数，而本人的惟一工作是简化原始问题，就假如递归办法曾经是实现的，要思考的是如何应用这个曾经存在的递归办法；

Leetcode206 题

给你单链表的头节点 `head`，请你反转链表，并返回反转后的链表。

该题除了应用如下的迭代办法解决：

迭代办法

/**

 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) {this.val = val;}
 * ListNode(int val, ListNode next) {this.val = val; this.next = next;}
 * }
   */
   class Solution {public ListNode reverseList(ListNode head) {
       ListNode pre=null;
       ListNode cur=head;
       while(cur!=null){
           ListNode next=cur.next;
           cur.next=pre;
           pre=cur;
           cur=next;
       }
       return pre;
   }
   }

还能够应用递归的形式实现，代码更加简洁：

递归办法

 /**
 
  * Definition for singly-linked list.
  * public class ListNode {
  * int val;
  * ListNode next;
  * ListNode() {}
  * ListNode(int val) {this.val = val;}
  * ListNode(int val, ListNode next) {this.val = val; this.next = next;}
  * }
    */
    class Solution {public ListNode reverseList(ListNode head) {if(head==null){return head;// 如果以后节点为空则间接返回 head}
        ListNode newHead = reverseList(head.next);
        head.next.next = newHead;
        head.next = null;
        return newHead;
    }
    }

递归过程的调用以上图为例，小问题为对前面的节点进行反转，则 reverseList 返回的后果 newHead 就是前面的子链表反转后的后果，于是使反转失去的 newHead 的 next 指向以后的 head，就实现了最简问题的反转，并使 Head 的 next 指向 null。不要去纠结递归过程是怎么的，只有认为 reverseList 函数是一个曾经存在的魔法函数并应用它的性能。

当然，应用递归的前提是它满足递归的几个条件：①能够大问题分成完全相同解决办法的小问题；②有终止条件③能调用本身。

数学归纳法（Mathematical Induction, MI）是一种数学证实办法，通常被用于证实某个给定命题在整个（或者部分）自然数范畴内成立。

最简略和常见的数学归纳法是证实当 n 等于任意一个自然数时某命题成立。证实分上面两步：

证实当n= 1 时命题成立。
假如 n=m 时命题成立，那么能够推导出在 n=m+ 1 时命题也成立。（m 代表任意自然数）

这种办法的原理在于：首先证实在某个终点值时命题成立，而后证实从一个值到下一个值的过程无效。当这两点都曾经证实，那么任意值都能够通过重复应用这个办法推导进去。把这个办法想成多米诺效兴许更容易了解一些。例如：你有一列很长的直立着的多米诺骨牌，如果你能够：

证实第一张骨牌会倒。
证实只有任意一张骨牌倒了，那么与其相邻的下一张骨牌也会倒。

那么便能够下结论：所有的骨牌都会倒下。

数学归纳法中，n=1、2、3…N 时，每一个 n 都映射于一个同样构造的问题，即从小问题始终归纳到大问题，g(n+1)=f(n)；

接下来思考递归，递归工作时，个别会从大问题开始，始终执行到小问题，再层层返回参数。就像一个人关上一个门外面还有一个，始终开到最初一个门（达到递归终止条件），而后从最初一个门往回走，每出一个门就带回一个门的信息，直到回到初始门，实现每个门的信息处理。返回参数的过程就像数学归纳法从小到大的演绎过程。

不同之处是，数学归纳法咱们能够很分明地晓得每一步是如何运作计算的，而递归的过程比拟难以想象，而递归过程并不是代码编写者须要关注的事，把递归函数当作一个曾经具备指标要求性能的魔法函数，用就能够了。

递归函数必须要有 终止条件：要使一个递归办法失常工作，必须使其对于越来越简略的示例不能有有限的演绎序列；递归演绎必须能失去一个能够用其余办法失去的根本状况，否则递归会有限循环上来。

确定递归函数的参数和返回值。
确定好哪些参数在传递过程中须要解决就在递归函数中加上这些参数，并且明确每次递归的返回值是什么，进而确定递归函数的返回类型。
确定终止条件。
写完递归算法，程序运行的时候常常会遇到栈溢出的谬误，起因是没写终止条件或者终止条件谬误。操作系统执行递归时也是要用栈的接哦古保留每一层递归的信息的，如果递归没有终止，那么操作系统的内存必然会溢出。
确定单层递归的逻辑。
确定每一层递归须要解决的信息。在这里会反复调用函数自身来实现递归过程。

正文完