[算法系列] 搞懂递归, 看这篇就够了 !! 递归设计思路 + 经典例题层层递进

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[算法系列] 搞懂递归, 看这篇就够了 !! 递归设计思路 + 经典例题层层递进，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含10640字，纯文字阅读大概需要16分钟。

内容图文

[算法系列] 搞懂递归, 看这篇就够了 !! 递归设计思路 + 经典例题层层递进

从学习写代码伊始, 总有个坎不好迈过去, 那就是遇上一些有关递归的东西时, 看着简短的代码, 怎么稀里糊涂就出来了. 今天我们就来好好好探讨递归这个东西. 本文结合他的相关概念,引出有关递归程序设计的一些例子,并加以说明, 其旨在更好地理解递归,使用递归.

0 什么是递归?

很多文章对于递归有很深刻的字面上的解释, 比如一个函数重复调用自身, 什么递过去再调回来之类的. 下面, 我们从自身调用来谈起吧 :

def f(i):
	f(i-1)    
f(5)

在f()定义中自身调用了f , 并将之前的参数i - 1 传入f . 因此不难知道 f(5)运行时是这样的 :

f(5) --> f(4) --> f(3) --> f(2) --> ... f(-∞)

不断地调用自身, 并且参数减1. 单纯地这样调用实际上并不满足递归, 当然, 我们的问题也不可能得以解决的哦.

回到设计程序初 : 我们设计程序时, 这个传入参数 i 是我们为解决眼前问题时的规模 , i - 1 是小一号的问题的规模 . 比如: 我们令f(i) 为 某人花掉 i 元钱 . 那么f(i) 在自身 调用f(i - 1) 时相当于 自己先花掉1 元后 ,将剩下的 i - 1元钱给另一个人用. 显然, 钱不可能为负, 因此总有被花光的时刻(i = 0 时应当终止), 相应的, 重复自身调用也有终止的一刻 , 也即是说, 递归要有出口 :

def f(i):
    if i == 0 :
        return
    f(i - 1)

在花钱函数中增加了一个判断 , 如果i =0 了 ,就return. 这就表示当一个人拿到钱的数目为0 , 他得上报(return)给之前调用给他的那个人,然后层层上报, 报给最初的那个人.

与此同时, 我们在缩减问题规模时, 可能并不是像上述例程那样, 什么都不做就直接i - 1 , 而是会"花一块钱" , 这其实就是我们所说的递归的 副作用. 注意, 这是我们在问题规模减小时所加的副作用, 当钱用光了,层层上报时 , 能不能也有副作用呢? 答案是显然是肯定的. 我喜欢把这两种副作用称之为 递过去过程中的副作用 和 归回来过程中的副作用

上述部分说明了:

1. 什么是递归 ----- 函数自己调用自己.
2. 注意死循环 ------ 递归要有出口
3. 递归往往有副作用 ----- 递过去途中 的 和 归来途中, 其中递过去往往是问题规模缩小的过程, 归来过程是已经触及到出口后的返回

知道了什么是递归那么我们怎么来设计递归呢?

1. 找重复, 思考问题规模如何缩小
2. 找变化
3. 找边界, 就是递归出口了

下面为了更好地体会下递归并说明上述三条 , 将下列问题用递归方式表达

求n的阶乘

1. 找重复: n的阶乘 = n * (n - 1的阶乘), 那么 求 "n - 1的阶乘"就是原问题的重复 – 子问题
2. 找变化: 这里就是n的量越变越小 – 变化的量往往作为参数
3. 找边界: 出口, 找一个数的阶乘, 不可能小于1

def jiecheng(n):
    if(n == 1 ):
    	return 1
    return n * jiecheng(n - 1)

顺序打印 i 到 j ( i <= j , 包含j)

这个问题显然可以不用递归方式来做, 但是这里正是通过使用递归来体会: 自己做一部分, 剩下的交给别人按同样的方式来处理, 然后等待处理结果, 再加上自己处理的结果

1. 找重复:
2. 找变化: 这里就是n的量越变越小 – 变化的量往往作为参数
3. 找边界: 出口, 即 i = j 时

def print_i_j(i , j ):
    if(i > j):
        return
    print(i)
    print_i_j(i +1 , j)

我们再看看这个递归写法: 在没到达出口条件时: 先打印出i , 再调用 小一号规模的问题. 下面是调用结果:

print_i_j(1,10)
#1 2 3 4 5 6 7 8 9 10 

倒序打印 i 到 j ( i <= j , 包含j)

实际上, 我只需在上述代码中调换下打印顺序即可解决该问题:

def print_i_j(i , j ):
    if(i > j):
        return
    print_i_j(i +1 , j)
    print(i, end=" ")

现在来分析下print(i)放在下一次调用之前和之后的情况:

• 顺序打印: 先打印出i ,再自身调用小一号规模的子问题, 这就相当于是自己先处理一些,剩下的交给其他人处理(先花1元钱, 剩下的交给下一个人花) . 这也就是所谓的 在递出去时产生的副作用

• 倒序打印: 先调用小一号的子问题, 由于在自身调用前, 也就是"递出去时"没有其余动作, 重复调用会直至递归出口, 然后依次返回, 子函数在反回到父函数时会接着父函数调用位置的下一行继续执行, 这就是所谓的 在归回来的产生的副作用 .

  倒序时, 先一鼓作气走到了 i > j 然后返回这一轮的父函数中, 此时是 i = j ,紧接着print(i) 也就是j 的值了 , 然后再返回他的父函数中, i = j - 1 ,打印的也就是倒数第二个数了.

下面我们继续

对数组 arr 所有元素进行求和

这个很显然也是可以 for 循环进行, 不过我们就是要改成递归, 体会自己做一部分工作, 剩下的(小一号规模的子问题)交给和自己具有相同功能的人(自我调用)来做.

下面是该问题的一个设计思考

def sum(arr):
    ...

发现我们很在在递归内部继续写, 这是为什么呢? 原因就在于, 这个arr参数是不变的 . 参考:找变化: 变化的量往往作为参数 这一点. 在求和范围不断缩小时, 我们需要一个参数去描述

我们需要在不变中追求统一, 在变化中寻求突破(出口) (是不是很哲学♂ )

def sum(arr , begin):
    if begin == len(arr) - 1:
        return arr[begin]
    return  arr[begin] + sum(arr , begin + 1)

在递归中, begin从0开始不断地增加, 直到到达最后一个元素下标为止.

上述例子也就很好的说明了递归中的变与不变, 而在变化中添加参数也是递归设计的难点 , 下面再来个这种例子:

给定一个字符串,将其翻转

例如输入: “abcd” , 输出"dcba"

def reverse(str , end):
    if end == 0:
        return str[0]
    return str[end] +reverse(str ,  end - 1)

end从str的最后一位下标开始往回,直到0

现在,各位有无对递归设计思想中的 :变化中寻找重复构以成递归, 重复中寻找变化以靠近出口有了更深的理解了呢?

---

前面的递归设计中, 我们可以将其统称为: 求解f(N),我们自己做一部分x, 其他的交给和我同样功能的人做f(N- 1),直到分不了为止. 换句话说, 为求解f(N),我们可以先求解缩小一次规模的问题f(N-1), 加之一些副作用x. 如下:

f(N) = x + f(N - 1)

在递归中, 除了上面那种缩小一点问题规模,带点副作用,再缩小 … 还有将问题 拆分成两个子问题去分别求解的,比如:

f(N) = f(N/2) + f(N/2) + X  		#将问题N拆成两半,分别求解f(N/2)
f(N) = f(N - 1) + f(N - 2) + x		#为求解f(N),需要的比现在小1号的子问题f(N-1)和小2号的子问题f(N-2)
f(N) = f(N/k) + f(N/k) + f(N/k) + ...

求第n 个斐波那契数列元素

斐波那契数列 1,1,2,3,5,8,13 ,… , 我们发现从第三项开始, 该位置上的值等于其前面两个位置值的和

即有天然的 f(n) = f(n - 1) + f(n -2) ,当n >= 3时, 当要求解n时, 我们只需要分别求解n-1 和 n - 2 的结果,再相加即可.

def fibo(n):
    if n <= 2:
        return 1
    return  fibo(n -1) + fibo(n -2)

print(fibo(6))

这里面的出口即为n = 1或者2 时, 他们是天然等于1的. 变化的即为这个n 了 ,不变的是求解方法: 每一项等于前面两项的和.

(细心的同学可以发现, 每次我们在求f(n -1) 和 f(n -2)时 ,是分别进行递归的, 因此很多东西实际上是重复计算了的, 而f(n - 1) 实际上只需要f(n-2) + (n-1)即可求得, 这其实涉及到记事本方法, 也是dp方法的一个重要例子, 以后有机会会继续更新的~~)

求解最大公约数

两个数m , n ,若 m % n = 0 则n为两个数的最大公约数 (出口)

若 m % n = k (k != 0) 则求 n % k (变化)

def gcd(m ,n ):
    if n == 0:
       return m
	return gcd(n , m%n)

插入排序的递归形式

# 插入排序的递归形式
def insert_sort(arr , k):
    if k == 0 :
        return ;
    #对前n -1 个元素排序
    insert_sort(arr, k -1)
    # 把位置k的元素插入到前面的部分
    x = arr[k]
    index = k -1 
    while  index > -1 and x <arr[index] :
        arr[index + 1] = arr[index]
        index -= 1
    arr[index+1] = x

大体思路和非递归的循环式的差不多, 递归式的是先从k=len -1出发, 然后径直走到0处, 依次向前插到合适的位置, 逐渐归回来,即k增加.

递归设计思路小结:

找重复:

1. 找到一种划分成更小规模问题的方法, 或者是单个划分,或者是多个划分, 另外也可能选择划分
2. 找到递推公式或者等价转换

找变化:

? 变化的量通常会作为参数,(循环的过程也是变化)

找出口:

? 变化的极限往往就是出口.(循环的中点就是出口)

汉诺塔问题

文字描述: 将 1 ~ N 从A 移动到B, C作为辅助 . 要求一次只能移一个, 小的不能在大的下面 (最下面一个为N)

按照思路小结,先尝试把问题规模缩小, 找一种划分方法:

• 考虑把1 和 2 ~ N 划分开 . 那么完成这件事情需要三个步骤:

  1. 把 1 直接从A挪到C
  2. 把 2 ~ N 从A挪到B , C作为辅助
  3. 把 1 直接从C挪到B

  现在重点关注第2点, 考虑: 把2 ~ N 挪到B 这一事件是否是把1 ~ N 挪到B的子问题呢?

  我们发现, 把1 ~ N 挪到B , B和C都为空, 两个位置都能放盘子, 但在2 ~ N 从A挪到B时 , C上面有1, 根据题意小盘上面不能放大盘, 因此此时2 ~ N不能往C上放. 该问题的局面与初始不同, 第2点并不是原题等价缩小的规模

• 考虑把1 ~ N -1 和 N 划分开, 那么完成该事情同样需要三个步骤:

  1. 把1 ~ N -1 从 A 挪到 C上 , B 作为辅助
  2. 把 N 从直接 A 挪到 B 上
  3. 把1 ~ N -1 从C 挪到 B 上 , A 作为辅助

  类似的, 我们关注第1 , 3 是否为1 ~ N 从A 挪到B的子问题.

  显然, 把1 ~ N -1 从A挪到C具有相同的局面(其余两个位置随便放). 把1 ~ N -1 从C 挪到B需要考虑下: 此时 N 在 B 上, 但是他是最大的, 对于在C上的1 ~ N -1 , 也是A,B两个位置都能放的, 由此可见, 此处问题即上一个的子问题.

  各位现在可以看看汉诺塔文字描述的加粗部分和上面的1,3, 子问题规模性已经说明.

接下来尝试找变化, 从上述加粗的子问题父问题描述我们发现 ,变化的其实包括有 待转移盘个数N 变为N -1 , 从哪转移到哪(from A to C), 那好 ,把这些作为参数.

最后考虑出口, 显然, 当N =1 时 , 直接从A移动到B即可.

def hano_tower(N , src , dis , help):
    '''
    :param N: 初始的N个从小到大的盘子, N 是最大编号
    :param src: 原始位置
    :param dis: 目标位置
    :param help: 辅助位置
    '''
    if N == 1:
        print("移动第 " + str(N) + " 个盘子, 从 " + src + " 到 "+ dis)
	    return
    else:
        hano_tower(N -1 , src , help , dis) #先把 N - 1 个盘子挪到辅助空间
        print("移动第 " + str(N) + " 个盘子, 从 " + src + " 到 " + dis)
        hano_tower(N -1 , help , dis , src) #先把 N - 1 个盘子挪到辅助空间

hano_tower(3 , "A" , "B" , "C")
#控制台输出
移动第 1 个, 从 A 到 B
移动第 2 个, 从 A 到 C
移动第 1 个, 从 B 到 C
移动第 3 个, 从 A 到 B
移动第 1 个, 从 C 到 A
移动第 2 个, 从 C 到 B
移动第 1 个, 从 A 到 B

二分查找的递归法

等价为子问题:

1. 左边找 (递归)

2. 中间找 (是否等于中间那个数)

3. 右边找 (递归)

   注意, 左查找和右查找只选其一

变化的量, 左右两边界low, high作为参数. 变化中, 两者靠近, 当low > high 时 或者 找到了k 时即为出口

def binary_search(k,arr, low, high):
   mid = int((low + high) /2)
   if(low > high):
       return -1
   if arr[mid] == k:
       return mid
   elif arr[mid] > k:
       return binary_search(k ,arr , low , mid - 1 )
   else:
       return binary_search(k ,arr , mid +1, high  )

bin_arr = [1,2,3,5,6,7,9,11,13,16]
print(binary_search( 7, bin_arr, 0 , len(bin_arr) - 1))

以上是一些熟悉的例子, 通过一些常见的问题修改成递归形式的过程中, 了解了递归设计的方法, 下面是一些经典的递归设计练习

1. 青蛙上楼梯

楼梯有n个台阶, 一个青蛙一次可以上1 , 2 或3 阶 , 实现一个方法, 计算该青蛙有多少种上完楼梯的方法

令f(n) 为 青蛙上n阶的方法数. 则f(n) = f(n -1) +f(n - 2) + f(n -3) , 当n >= 3

什么意思呢? 假如青蛙上10 阶, 那么其实相当于要么 站在第9 阶向上走1步,要么 站在第8 阶向上走两步, 要么在第7阶向上走3步.

进一步来说, 青蛙在到达第10阶的方法数, 即为到达第9阶的方法数加上到第8阶的方法数上加第7阶的方法数的和, 则有子问题:

求解f(n):
	求解f(n-1)
	求解f(n-2)
	求解f(n-3)
	三者相加	

找变化: 变化的即为台阶数n

找出口: 当n = 0 时 ,青蛙不动 , f(0) = 0; n = 1时 ,有1种方法 , n = 2 时 有2 种方法

def go_stairs(n):
    if n == 0 :
        return 0
    if n == 1:
        return 1
    if n == 2:
        return 2
    return go_stairs(n - 1) +go_stairs(n - 2) +go_stairs(n -3)

2 . 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾, 我们称之为数组的旋转, 输入一个递增排序的数组的一个旋转, 输出旋转数组的最小元素. 例如{3,4,5,1,2}是{1,2,3,4,5}的一个旋转, 该数组的最小值为1.

def reverse_min(arr):
    begin = 0
    end = len(arr) - 1
    # 考虑没有旋转的 情况
    if arr[begin] < arr[end] :
        return arr[begin]
    # begin 和 end 指向相邻元素时,退出
    while begin + 1  < end :
        mid = int((begin + end) / 2)
        # 要么左侧有序, 要么右侧有序
        if arr[mid] >= arr[begin]:  #左侧有序, 在右边找
            begin = mid;
        else:
            end = mid
    return arr[end]

3. 设计一个高效的求a的n次方幂的算法

def pow(a , n):
    if n == 0 :
        return  1
    res = a
    ex = 1

    while (ex << 1 ) <= n:  # 翻倍后还小于n的话直接翻倍
        res= res * res
        ex =ex  * 2
    # 差n-ex次方还没有乘上结果
    return res * pow(a , n - ex) #将翻不动时的剩余的作为参数带到下一次运行

下一篇文章中, 我们将讨论递归的应用 – 分治法 . 应该说, 递归是一种编程形式, 而分治法是常常使用递归形式的一种算法.

• 点赞 1
• 收藏
• 分享
• • 文章举报

Lawfree 发布了43 篇原创文章 · 获赞 74 · 访问量 1万+ 私信 关注

内容总结

以上是互联网集市为您收集整理的[算法系列] 搞懂递归, 看这篇就够了 !! 递归设计思路 + 经典例题层层递进全部内容，希望文章能够帮你解决[算法系列] 搞懂递归, 看这篇就够了 !! 递归设计思路 + 经典例题层层递进所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---