精华内容
下载资源
问答
  • 什么是递归

    2019-12-02 01:11:10
    一、什么是递归? 二、为什么使用递归?递归的优缺点? 三、什么样的问题可以用递归解决呢? 四、如何实现递归? 1、递归代码编写 2、递归代码理解 五、递归常见问题及解决方案 六、如何将递归改写为非递归...

    目录

    一、什么是递归?

    二、为什么使用递归?递归的优缺点?

    三、什么样的问题可以用递归解决呢?

    四、如何实现递归?

    1、递归代码编写

    2、递归代码理解

    五、递归常见问题及解决方案

    六、如何将递归改写为非递归代码?


    一、什么是递归?

    1、递归是一种非常高效、简洁的编码技巧,一种应用非常广泛的算法,比如DFS深度优先搜索、前中后序二叉树遍历等都是使用递归。

    2、方法或函数调用自身的方式称为递归调用,调用称为递,返回称为归。

    3、基本上,所有的递归问题都可以用递推公式来表示,比如

    f(n) = f(n-1) + 1; 

    f(n) = f(n-1) + f(n-2);

    f(n)=n*f(n-1);

     

    二、为什么使用递归?递归的优缺点?

    1、优点:代码的表达力很强,写起来简洁。

    2、缺点:空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题。

     

    三、什么样的问题可以用递归解决呢?

    一个问题只要同时满足以下3个条件,就可以用递归来解决:

    1、问题的解可以分解为几个子问题的解。何为子问题?就是数据规模更小的问题。

    2、问题与子问题,除了数据规模不同,求解思路完全一样

    3、存在递归终止条件

     

    四、如何实现递归?

    1、递归代码编写

    写递归代码的关键就是找到如何将大问题分解为小问题的规律,并且基于此写出递推公式,然后再推敲终止条件,最后将递推公式和终止条件翻译成代码。

    2、递归代码理解

    对于递归代码,若试图想清楚整个递和归的过程,实际上是进入了一个思维误区。

    那该如何理解递归代码呢?如果一个问题A可以分解为若干个子问题B、C、D,你可以假设子问题B、C、D已经解决。而且,你只需要思考问题A与子问题B、C、D两层之间的关系即可,不需要一层层往下思考子问题与子子问题,子子问题与子子子问题之间的关系。屏蔽掉递归细节,这样子理解起来就简单多了。

    因此,理解递归代码,就把它抽象成一个递推公式,不用想一层层的调用关系,不要试图用人脑去分解递归的每个步骤。

     

    五、递归常见问题及解决方案

    1、警惕堆栈溢出:可以声明一个全局变量来控制递归的深度,从而避免堆栈溢出。

    2、警惕重复计算:通过某种数据结构来保存已经求解过的值,从而避免重复计算。

     

    六、如何将递归改写为非递归代码?

    笼统的讲,所有的递归代码都可以改写为迭代循环的非递归写法。如何做?抽象出递推公式、初始值和边界条件,然后用迭代循环实现

     

     

     

    展开全文
  • 什么是递归递归做为一种算法在程序设计语言中广泛应用,它是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。递归算法一般用于解决三类问题:a.数据的定义是按递归定义的。(Fibonacci(斐波那契)...

    af8aaf23cdef99e390cdbea5cdd9d535.png

    什么是递归

    递归做为一种算法在程序设计语言中广泛应用,它是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。

    递归算法一般用于解决三类问题:

    a.数据的定义是按递归定义的。(Fibonacci(斐波那契)函数)

    b.问题解法按递归算法实现。(回溯)

    c.数据的结构形式是按递归定义的。(树的遍历,图的搜索)

    学习视频教程分享:java教学视频

    例子:

    这是一个排列的例子,它所做的工作是将输入的一个字符串中的所有元素进行排序并输出

    例如:你给出的参数是”abc” 则程序会输出: abc acb bac bca cab cba a

    算法的出口在于:low=high也就是现在给出的排列元素只有一个时。

    算法的逼近过程:先确定排列的第一位元素,也就是循环中i所代表的元素, 然后low+1开始减少排列元素,如此下去,直到low=high

    示例如下:public class Foo {

    public static void main(String[] args) {

    permute(“abc”);

    }

    public static void permute(String str) {

    char[] strArray = str.toCharArray();

    permute(strArray, 0, strArray.length – 1);

    }

    public static void permute(char[] list, int low, int high) {

    int i;

    if (low == high) {

    String cout = “”;

    for (i = 0; i <= high; i++){

    cout += list[i];

    System.out.println(cout);

    }

    }else {

    for (i = low; i <= high; i++) {

    char temp = list[low];

    list[low] = list[i];

    list[i] = temp;

    permute(list, low + 1, high);

    temp = list[low];

    list[low] = list[i];

    list[i] = temp;

    }

    }

    }

    }

    相关文章教程推荐:java编程入门

    展开全文
  • 什么是递归算法:对递归的理解!递归算法是一种直接或者间接调用自身函数或者方法的算法。Java递归算法是基于Java语言实现的递归算法。递归算法的实质是把问题分解成规模缩小的同类问题的子问题,  一、基本概念  ...
  • 什么是递归?先了解什么是递归. 欢迎阅读我的个人博客,有更好的排版和文章:https://pushy.site 1. 介绍 一说起递归,我想每个人都不陌生。举个从小就听过的例子:从前有座山,山里有座庙,庙里有个和尚,和尚...

    原文:https://www.cnblogs.com/Pushy/p/8455862.html

    什么是递归?先了解什么是递归.

    欢迎阅读我的个人博客,有更好的排版和文章:https://pushy.site

    1. 介绍

    一说起递归,我想每个人都不陌生。举个从小就听过的例子:从前有座山,山里有座庙,庙里有个和尚,和尚在讲故事,从前有座山,山里有座庙,庙里有个和尚,和尚在讲故事,从前有座山...

    还有你从两面相对的镜子中看到的画面,其实都是抽象出来的递归现象,但是严格来说并不是递归,因为会一直重复下去,没有终止条件,那就称为死循环了。有关递归和死循环的异同我们之后会说到,那么现在先来了解一下什么是递归?

    那么什么是递归呢? 要理解递归,就得先了解什么是递归,实际上这句话就是一个递归。这么说可能不好理解,接下来我举个简单的例子来解释这段话的意义。

    假设我们现在都不知道什么是递归,我们自然想到打开浏览器:输入到谷歌的网页,点击搜索递归,然后在为维基百科中了解到了递归的基本定义。在了解到了递归实际上是和栈有关的时候,你又蒙圈了,什么是栈呢?数据结构没学清楚,此时的你只能又打开谷歌,搜索什么是栈。接下来你依次了解了内存/操作系统。在你基本了解好知识之后,你通过操作系统了解了内存,通过内存了解了栈,通过栈了解了什么是递归这下你恍然大悟!原来这就是递归啊!

    这下应该有点明白了吧,这个过程其实就是递归的过程,如果不了解递归,那就先了解什么是递归,可能你会说这是个循环并不是递归,我们前面说到,递归是需要终止条件的,那么你明白递归是什么其实就是终止条件。整个过程,搜索引擎充当递归函数(只是形象的假设)。在你去依次查找递归/栈/内存/操作系统的过程为前行阶段,在你都了解完之后,反回去了解含义的过程为退回阶段。如果还是不太清楚,可以接着看下面的例子。

    2. 示例

    也许之前你在网络上看到过这张图片:

    xiaoliyu.jpg

    实际上这张图就很形象地表达出了递归,这句吓得我抱起了抱着抱着抱着我的小鲤鱼的我的我的我如果从字面意义上看可能看不出是什么意思,那么我们可以通过代码来实现同样的效果:

    function Recursion(depth) {
        console.log('抱着');
        if (!depth) {
            console.log('我的小鲤鱼')
        } else {
            Recursion(--depth);  // 递归调用
        }
        console.log('的我');
    }
    
    console.log('吓得我抱起了');
    Recursion(2)

    在终端的打印结果为如下,可以看到和上面的那段话是一样的:

    xiaoliyuconsole.png

    代码其实十分简单,但是需要理解的是:if代码块的条件(!depth)为递归调用的终止条件,在else代码块内递归调用函数.我们前面有说到递归的过程是存在前行和退回阶段的,那么在前行阶段我们在每次调用函数后,打印出了"抱着",并且当depth≠0时重新调用该函数;在退回阶段,将会去执行代码console.log('的我');再打印出"的我".

    褚跃跃的图也能比较清楚地反映出这个过程:

    enterReturn.jpg

    好了!这下你应该明白什么是递归了吧?如果你还没有明白什么是递归的话,你可以看什么是递归?

    3. 应用

    3.1 斐波拉契数列

    有关递归应用的应用有很多,例如注明的斐波拉契数列就可以通过递归来实现:

    def fib(x):
        if x < 2:
            return 0 if x == 0 else 1
        # 当x > 2时,开始递归调用fib()函数:
        return fib(x - 1) + fib(x - 2)
    
    print(fib(6))  # 打印结果为:8

    这里需要对i<2时的特殊情况做出判断,当x==0时,直接返回0,当x==1时,直接返回1

    3.2 遍历文件

    首先我们需要了解遍历的算法:定义的file_display函数以某个目录(/home/pushy)作为遍历的起点.遇到一个子目录时,就先接着遍历子目录(递归调用函数)。遇到一个文件时,就直接对改文件进行操作(这里只打印出文件的文件名):

    import os
    
    def file_display(filepath):
        for each in os.listdir(filepath):
            # 得到文件的绝对路径:
            absolute_path = os.path.join(filepath, each)
            # 得到是否为文件还是目录的布尔值:
            is_file = os.path.isfile(absolute_path)
            if is_file:
                # 当前的绝对路径为文件:
                print(each)
            else:
                # 当前的绝对路径为目录:
                file_display(absolute_path)
    
    file_display('/home/pushy')

    这样我们就可以遍历到/home/pushy路径下的所有文件:

    readFile.png

    另外我们还可以使用递归来创建目录:

    import os
    
    def createFile(dirname):
        exits = os.path.exists(dirname)
        if exits:
            return True
        else:
            # 开始递归调用函数,并接受其返回值:
            rec_result = createFile(os.path.dirname(dirname))
            if rec_result:
                # 如果不存在该目录,则创建dirname的目录,并返回已经创建(存在)的值True:
                os.mkdir(dirname)
                return True
    
    createFile('./aa/bb/cc')

    4. 循环与递归

    好了,递归的知识差不多介绍完了。如果看完上边大概已经了解了循环和递归的区别了。对了!简单来说,循环是有去无回,而递归则是有去有回(因为存在终止条件)。

    举个栗子,你用你手中的钥匙打开一扇门,结果去发现前方还有一扇门,紧接着你又用钥匙打开了这扇门,然后你又看到一扇们...但是当你开到某扇门时,发现前方是一堵墙无路可走了,你选择原路返回——这就是递归

    但是如果你打开一扇门后,同样发现前方也有一扇们,紧接着你又打开下一扇门...但是却一直没有碰到尽头——这就是循环。

    展开全文
  • 什么是递归?用Java写一个简单的递归程序递归的定义递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来解决。递归的要素自定义递归函数,并确定函数的基本功能例如Java从键盘输入一个...

    什么是递归?用Java写一个简单的递归程序

    递归的定义

    递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来解决。

    递归的要素

    自定义递归函数,并确定函数的基本功能例如Java从键盘输入一个数,求输入这个数的阶乘。这个时候把输入的数字作为形参int diGuiTest(int n ){} 找到递归函数循环结束条件在求阶乘的时候,我们不妨做出如下思考,例如输入的n是5,那么5!是5 * 4 3 * 2 * 1,那是不是可以写成n f(n-1)?,程序运行过程如下:5* f(4)f(4)相当于重新调用了函数,形参为45 * 4* f(n-1)f(3)相当于重新调用了函数,形参为35 * 4* 3* f(n-1)f(2)相当于重新调用了函数,形参为25 * 4* 3 * 2* f(n-1)f(1)相当于重新调用了函数,形参为1很容易发现,这时候如果递归调用到n为1的时候,就要结束调用自身代码如下:int diGuiTest(int n ){if(n==1){return 1;}else{return n*f(n-1);}} 代码示例

    求1–100之间所有自然数的和int sum (int n ){if(n==1){return 1 ;}else{return n+sum(n-1);}}12345678斐波拉契数列斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2) (n ≥ 2,n ∈ N*)int fibonacci(int n ){if (n<=1){return n;}else {return fibonacci(n-1)+fibonacci(n-2);}} 汉诺塔问题首先我们考虑最简单的情况:将最上面的一块放到B,再将最下面一块放到C,再把最上面一块从B放到C即可

    2b1f66803b6a534b52071657a6cf2e06.png

    public class Hanio { public static void main(String[] args) { char A='A'; char B='B'; char C='C'; hannio(3,A,B,C); } static void hannio(int paltfrom,char A,char B, char C){ if (paltfrom==1){ move (A,C); }else { hannio(paltfrom-1,A,C,B);//上面两个盘子,通过C柱到B柱 move (A,C); hannio(paltfrom-1,B,A,C);// } } static void move(char A,char B){ System.out.println(A+"---->"+B); }}

    展开全文
  • 什么是递归 一个事物由这个事物的本身所构建,那么在理解这个事物的时候,就需要理解这个事物的构造方式,那么就需要回到理解这个事物的本身,从而再次需要理解这个事物的构成……这个不断循环理解的过程就形成了...
  • 什么是递归

    2020-06-30 11:16:50
    什么是递归? 递归的实现就是在函数内部调用函数本身,递归必须有结束的条件,不然会陷入死循环。
  • java中的递归是什么发布时间:2020-06-18 14:02:17来源:亿速云阅读:94作者:鸽子什么是递归递归做为一种算法在程序设计语言中广泛应用,它是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。...
  • 什么是递归函数

    2020-07-11 14:39:55
    什么是递归函数 在编程的世界里面,递归就是一个自己调用自己的手段 递归函数:一个函数内部,调用了自己,循环往复,递归函数和循环很类似 要实现递归必须要书写两个内容: 一个是满足结束条件的时候结束函数 一个是...
  • 2.1什么是递归 1.递归的定义 递归:在函数的定义中又调用函数自身的方法。 尾递归:递归调用函数在最后一句语句 递归满足条件: ①可以由大问题转换成小问题 ②调用次数有限 ③有结束递归的语句 什么时候使用递归?...
  • 什么是递归?用Java写一个简单的递归程序

    千次阅读 多人点赞 2021-02-17 14:33:45
    什么是递归?用Java写一个简单的递归程序 递归的定义 递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来解决。 递归的要素 自定义递归函数,并确定函数的基本功能 例如Java从键盘...
  • 五分钟教你学会递归一、什么是递归?二、递归可以用来做什么?三、使用递归归类文件夹 一、什么是递归? 初次听到这个词语的时候,想必大家都很不理解,什么是递归呢?举个简单的例子,很多人都看过电影《盗梦空间》...
  • 聊一下什么是递归

    2019-11-09 00:19:47
    因为最近一些繁琐的事情,很久没有发博客了,其实这段时间我一直在想我要写些什么,思来想去,还是聊聊递归吧...什么是递归? 这就是递龟,就聊到这吧。 开个玩笑。 递归,通俗的说,就是函数自己调用自己的意思, ...
  • 什么是递归?优缺点是啥?

    千次阅读 2019-09-03 13:06:37
    文章目录什么是递归?区别循环与递归从斐波那契数列数列来看递归参考文献 什么是递归? 简单讲就是函数调用自己。 递归就是有去(递去)有回(归来)。 下图来自于 什么是递归?先了解什么是递归. 怎么更...
  • 什么是递归?用Java写一个简单的递归程序递归的定义递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来解决。递归的要素自定义递归函数,并确定函数的基本功能例如Java从键盘输入一个...
  • 什么是递归?用Java写一个简单的递归程序递归的定义递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来解决。递归的要素自定义递归函数,并确定函数的基本功能例如Java从键盘输入一个...
  • 然后,你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,你可以回答出你到底用这你把钥匙打开了几扇门1、定义 (什么是递归?)在数学与计算机科学中,递归(Recursion)是指在函数的定义中使用函数自身的方....
  • 什么是递归,递归的优缺点Prerequisite: Recursion in C language 先决条件: C语言递归 递归函数 (Recursive function ) A function which calls itself is a recursive function. There is basically a ...
  • 什么是递归?用Java写一个简单的递归程序递归的定义递归(recursion):以此类推是递归的基本思想,将规模大的问题转化为规模小的问题来解决。递归的要素自定义递归函数,并确定函数的基本功能例如Java从键盘输入一个...
  • 认识递归之前,你首先得认识递归 如果你还不知道什么是递归,请你 点击
  • 1… 什么是递归? 方法自己调用自己,称为递归,该方法称为递归方法 package season6; public class TestDiGui { public static void main(String[] args) { System.out.println(calc(2,5)); System.out....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,706
精华内容 5,482
关键字:

什么是递归