算法策略 - 递归(Recursion)_玉树临风你卓哥的博客-程序员宅基地

技术标签: 数据结构与算法  

  • 递归:函数(方法)直接或间接调用自身。是一种常见的编程技巧
int sum(int n) {
    
    if (n <= 1) return n;
    return n + sum(n - 1);
}
void a(int v) {
    
    if (v < 0) return;
    b(--v);
}
void b(int v) {
    
    a(--v);
}

递归现象

在这里插入图片描述

函数的调用过程

在这里插入图片描述

函数的递归调用过程

在这里插入图片描述

  • 如果递归调用没有终止,将会一直消耗栈空间
    最终导致栈内存溢出(Stack Overflow)
  • 所有必需要一个明确的结束递归的条件
    也叫作边界条件、递归基
    在这里插入图片描述

实例分析

在这里插入图片描述

  • 注意:使用递归不是为了求得最优解,是为了简化解决问题的思路,代码会更加简洁
  • 递归求出来的很有可能不是最优解,也可能是最优解

递归的基本思想

  • 拆解问题
  1. 把规模大的问题编程规模较小的同类型问题
  2. 规模较小的问题又不断变成规模更小的问题
  3. 规模小到一定程度可以直接得出它的解
  • 求解
  1. 由最小规模问题的解得出较大规模问题的解
  2. 由较大规模问题的解不断得出规模更大问题的解
  3. 最后得出原来问题的解

在这里插入图片描述

  1. 凡是可以利用上述思想解决问题的,都可以尝试使用递归
  2. 很多链表、二叉树相关的问题都可以使用递归来解决
  3. 因为链表、二叉树本身就是递归的结构(链表中包含链表,二叉树中包含二叉树)

递归的使用套路

  1. 明确函数的功能
    先不要去是靠里面代码怎么写,首先搞清楚这个函数干嘛用的,能完成什么功能?
  2. 明确原问题与子问题的关系
    寻找f(n)与f(n-1)的关系
  3. 明确递归基(边界条件)
    递归的过程中,子问题的规模在不断减小,当小到一定程度时可以直接得出它的解
    寻找递归基,相当于是思考:问题规模小到什么程度可以直接得出解?

练习1 - 斐波那契数列

练习2 - 上楼梯(跳台阶)

练习3 - 汉若塔(Hanoi)


递归转非递归

  • 递归调用的过程中,会将每一次调用的参数、局部变量都保存在了对应的栈帧(Stack Frame)中
public static void main(String[] args) {
    
    log(4);
}
static void log(int n) {
    
    if (n < 1) return;
    log(n - 1);
    int v = n + 10;
    System.out.printIn(v);
}

在这里插入图片描述

  • 若递归调用深度较大,会占用比较多的栈空间,甚至会导致栈溢出
  • 在有些时候,递归会存在大量的重复计算,性能非常差
    这时可以考虑将递归转为非递归(递归100%可以转换成非递归)
  • 自己维护一个栈,来保护参数、局部变量
  • 但是空间复杂度依然没有得到优化
static class Frame {
    
    int n ;
    int v;
    Frame(int n, int v) {
    
        this.n = n;
        this.v = v;
    }
}
static void log(int n) {
    
    Stack<Frame> frames = new Stack<>();
    while (n > 0) {
    
        frames.push(new Frame(n, n + 10));
        n--;
    }
    while (!frames.isEmpty()) {
    
        Frame frame = freames.pop();
        System.out.printIn(frame.v);
    }
}
  • 在某些时候,也可以重复使用一组相同的变量来保护每个栈帧的内容
static void log(int n) {
    
    for (int i = 1; i <= n; i++) {
    
        System.out.printIn(i + 10);
    }
}
  • 这里重复使用变量i保存原来栈帧中的参数
  • 空间复杂度从O(n)降到了O(1)

尾调用(Tail Call)

  • 尾调用:一个函数的最后一个动作是调用函数
  • 如果最后一个动作是调用自身,称为尾递归(Tail Recursion),是尾调用的特殊情况
void test1() {
    
    int a = 10;
    int b = a + 20;
    test2(b);
}
void test2(int n) {
    
    if (n < 0) return;
    test2(n - 1);
}
  • 一些编译器能对尾调用进行优化,以达到节省栈空间的目的
    在这里插入图片描述
  • 下面代码不是尾调用
int factorial(int n) {
    
    if (n <= 1) return n;
    return n * factorial(n - 1);
}
  • 因为它最后1个动作是乘法

尾调用优化(Tail Call Optimization)

  • 尾调用优化也叫做尾调用消除(Tail Call Elimination)
  1. 如果当前栈帧上的局部变量等内容都不需要用了,当前栈帧经过适当的改变后可以直接当作被尾调用的函数的栈帧使用,然后程序可以jump到被尾调用的函数代码
  2. 生成栈帧改变代码与jump的过程称作尾调用消除或尾调用优化
  3. 尾调用优化让位于尾位置的函数调用跟goto语句性能一样高
  • 消除尾递归里的尾调用比消除一般的尾调用容易很多
  1. 比如Java虚拟机(JVM)会消除尾递归里的尾调用,但不会消除一般的尾调用(因为改变不了栈帧)
  2. 因此尾递归优化相对比较普遍,平时的递归代码可以考虑尽量使用尾递归的形式

尾调用优化前的汇编代码(C++)

void test(int n) {
    
    if (n < 0) return;
    printf("test - %d\n", n);
    test(n - 1);
}

在这里插入图片描述

尾调用优化后的汇编代码(C++)

在这里插入图片描述

尾递归示例1 - 阶乘

  • 求n的阶乘1*2*3* … *(n - 1)*n (n>0)
int factorial(int n) {
    
    if (n <= 1) return n;
    return n * factorial(n - 1);
}
int factorial(int n) {
    
    return factorial(n, 1);
}
int factorial(int n int result) {
    
    if (n <= 1) return result;
    return factorial(n - 1, n * result);
}

尾递归示例2 - 斐波那契额数列

int fib(int n) {
    
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);
}
int fib(int n) {
    
    return fib(n, 1, 1);
}
public int fib(int n, int first, int second) {
    
    if(n <= 1) return first;
    return fib(n - 1, second, first + second);
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/songzhuo1991/article/details/103233322

智能推荐

linux用rdate命令实现同步时间_skate的博客-程序员宅基地

author:skatetime:2010-05-07 用rdate命令实现同步时间 前两天说到用ntp时间服务器和ntpdate命令同步时间,今天简单记录下用rdate同步时间http://blog.csdn.net/wyzxg/archive/2010/05/06/5561548.aspx   在各种linux中都有rdate命令 1. 选在

WPF窗口启动时最大化_weixin_30613727的博客-程序员宅基地

在xaml对应的后台代码文件的初始化方法中: public ShellView() { InitializeComponent(); #region 启动时串口最大化显示 Rect rc = SystemParameters.WorkArea; //获取工作区大小 ...

mac 安装pyenv(python 多版本控制工具)_砚子丫的博客-程序员宅基地

git clone https://github.com/yyuu/pyenv.git ~/.pyenv配置环境变量# 编辑环境变量文件,没有就新建vim ~/.bash_profile# 配置文件内容export PATH="/Users/v_liangshuyan/.pyenv/bin:$PATH"if which pyenv &gt; /dev/null; then eval "$(pyenv init -)";fi# 使环境变量生效source ~/.bash_profi.

学习使用 python 中的 opencv 库 ----Sobel算子边缘检测应用车牌号识别_zhouchao2013的博客-程序员宅基地

欢迎使用Markdown编辑器写博客在python中的Sobel函数原型:def Sobel(src, ddepth, dx, dy, dst=None, ksize=None, scale=None, delta=None, borderType=None)前四个是必须的参数: - 第一个参数是需要处理的图像; - 第二个参数是图像的深度,-1表示采用的是与原图像相同...

c语言编写程序x的y次方,C语言变为编程y = x-x立方/ 3! + x五次方力量/ 5! -x7th power / 7!..._weixin_39631572的博客-程序员宅基地

这似乎不对,但是无论如何,我只是想补充一个问题,如果可以的话,您能再帮我一次吗?您不能采用它,但不要说我的代码是错误的!结果留在那里,我自己看了一下. 它不是正整数(x)的序列,被写了n次,怎么可能是错误的呢?我说的“不太正确”,我将再次更改它. n在正整数范围内. 我的答案n和x是通过键盘输入的!double f(double x,int n){如果(n == 0)返回0;int i;doubl...

python---get/post请求下载指定URL返回的网页内容,出现gzip乱码处理。设置Accept-Encoding为gzip,deflate,返回的网页是乱码_徐为波的博客-程序员宅基地

python—get/post请求下载指定URL返回的网页内容,出现gzip乱码处理。设置Accept-Encoding为gzip,deflate,返回的网页是乱码1、脚本# --*-- coding:utf-8 --*--#coding:utf-8import stringimport urllibimport urllib2import ssldef getpicyan

随便推点

jzxx_1174 [USACO] 麦香牛块_ckmoonfish的博客-程序员宅基地

题目描述农夫约翰的奶牛几乎要武装暴动,因为他们听说麦当劳要推出新产品麦香牛肉。奶牛们要尽力阻止这种产品的上市。他们研究了一种“劣等包装”策略。奶牛们说:“如果麦香牛肉有3块,6块以及10块装这三种,那么想买 1, 2, 4, 5, 7, 8, 11, 14, 或17块牛肉的顾客就得不到满足了。劣等的包装,劣等的产品!” 帮助奶牛们。给出N (不同包装的种类数, 1 输入第1行: N第2

Android完美解决cropper图片填充不满CropImageView导致截图错位_wellchang的博客-程序员宅基地

由于cropper截取计算左上坐标时没有考虑到图片比CropImageView小的情况,于是fork了一份并提交代码库地址:https://github.com/zhangwei911/cropper

用 visual studio code 开发 C++ 程序_BIBI2018的博客-程序员宅基地

翻译自:https://code.visualstudio.com/docs/languages/cpp译者受水平所限,如有错漏,敬请包涵2018/12这个 Microsoft C/C++ extension 插件为 Visual Studio Code 提供了C/C++ 的支持,这个插件使 Visual Studio Code 可以在 Windows、Linux、和 macOS 上跨平台开...

微服务整合Spring Security实现用户的认证和授权_垂钓的小鱼1的博客-程序员宅基地_微服务整合springsecurity

一、Spring Security介绍1、框架介绍Spring 是一个非常流行和成功的 Java 应用开发框架。Spring Security 基于 Spring 框架,提供了一套 Web 应用安全性的完整解决方案。一般来说,Web 应用的安全性包括用户认证(Authentication)和用户授权(Authorization)两个部分。(1)用户认证指的是:验证某个用户是否为系统中的合法主体,也就是说用户能否访问该系统。用户认证一般要求用户提供用户名和密码。系统通过校验用户名和密码来完成认证过程。

GitHub Pages自定义域名后每次hexo d都会失效解决_Ahri-情书的博客-程序员宅基地

在GitHub Pages设置自定义域名之后,发现每次hexo d 后都会失效,又要重新设置,太麻烦了。于是,问了一下牛皮的百度老师只要在source 目录添加一个新文件CNAME就好CNAME –不带任何后缀,这就是全称,里面写的是你的域名然后就ok了。怎么push都不用再去GitHub Pages设置了(^o^)/~...

python图像识别角度_Python Opencv实现图像轮廓识别功能_weixin_39821874的博客-程序员宅基地

本文实例为大家分享了python opencv识别图像轮廓的具体代码,供大家参考,具体内容如下要求:用矩形或者圆形框住图片中的云朵(不要求全部框出)轮廓检测Opencv-Python接口中使用cv2.findContours()函数来查找检测物体的轮廓。import cv2img = cv2.imread('cloud.jpg')# 灰度图像gray = cv2.cvtColor(img, cv2...

推荐文章

热门文章

相关标签