六、递归与回溯算法

在计算机领域里面，很多问题都可以要采用递归算法来解决。递归中，最长用到的方法就是回溯法。我们具体分析问题的时候，可以发现这类问题本质是一个树的形状。

一、递归算法

递归算法的本质还是将原来的问题转化为了更小的同一问题，进行解决。一般注意两点：
1、递归终止的条件。对应到了递归算法中最基本的问题，也是最最简单的问题。
2、递归过程。递归过程需要将原问题一步一步的推到更小的同一问题，更小的意思就是子问题解决起来就更加的简单。有写情况是能够找到一个递推的公式的。这个过程中就需要透彻的去理解递归函数的意义。明确这个函数的输入和输出是什么，这样来写的话，就清晰多了。

例子1、我们常见的斐波那契数列，这个例子算法用烂了
$f(n)=f(n-1)+f(n-2)$

因为有了这样的递归公式，那么我们就很容易的能看出来递归的终止条件就是我们知道的f(0)和f(1)了。有了f(0)和f(1)之后，我们就能够继续的递推出f(3)一直到f(n)了。
$f(0)=1$

$f(1)=1$

def fib(n):
    #递归的终止条件
    if n==0:
        return 1
    elif n==1:
        return 1    
    #递归的过程，已经有了现成的公式了，所以好写出来
    else:
        return f(n-1)+f(n-2)

例子2、对一个数组进行一个求和的操作
通常我们是用一个for循环就能够求出来一个数组的和是多少。也就是下面的简单的代码：

def Sum(nums):
    total=0
    for i in nums:
        total +=1
    return total

但是我们现在才用一个递归算法的思想来解决这个问题:
$\begin{eqnarray*} Sum(nums[0,\cdots,n-1])&=&Sum(nums[1,\cdots,n-1])+nums[0]\\ Sum(nums[1,\cdots,n-1])&=&Sum(nums[2,\cdots,n-1])+nums[1]\\ \cdots\\ Sum(nums[n-1,\cdots,n-1])&=&Sum([])+nums[n-1] \end{eqnarray*}$

# 函数定义为计算[left, ..., n)区间里面的所有元素的和
def Sum(nums, left):
    #递归的终止条件：left和nums数组长度时候，那么就没有求和的元素，所以我们就返回了0.
    if left==len(nums):
        return 0 
    #递归的逻辑部分，就是按照我们上面的递归公式了。
    else:
        return Sum(nums, left+1)+nums[left]

if __name__ =="__main__":
    test_arr = [1,2,3,4,5,6,7,8]
    print(Sum(test_arr), 0)  
    # 得到的结果就是36了

像我们常见的数据结构如链表、树、图等都是有着天然的递归结构的，链表由于是一个线性的结构，那么通常我们也是能够直接循环遍历就能解决问题的，但是这里我们用递归法来解决一下LeetCode上面的问题
LeetCode 203 移除链表元素
分析：链表的结构可以理解成一个节点连接这一个更短的链表，这样依次一直看下去，直到最后一个节点None，那么我们这个时候的递归终止条件就是head指向None了，返回的就是None

class Solution:
    # 我们的返回就是一个节点的指针
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        # 递归的终止条件就是head指向None的时候，返回None
        if head==None:
            return None
        # 递归的过程，要是head的val属性和要删除的元素的相等，那么就是返回了head的下一个节点，不相等的话，那么就留住它。
        head.next = self.removeElements(head.next, val)
        return head.next if head.val==val else head

二、回溯法

深入的理解递归算法之后，我们就开始进行回溯法的学习。通过LeetCode上面的几道题，我们来深入的探讨一下递归与回溯法的应用。

持续更新中...
数据结构与算法系列博客：
一、数据结构与算法概述
 二、数组及LeetCode典型题目分析
 三、链表（Linked list）以及LeetCode题
 四、栈与队列（Stack and Queue
五、树（Trees）
六、递归与回溯算法
 七、动态规划
 八、排序与搜索
 九、哈希表

参考资料
1、
2、
3、

最后编辑于：2019.08.01 09:38:17