递归算法 订阅
递归算法(英语:recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题,因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环,因此在很多函数编程语言(如Scheme)中习惯用递归来实现循环。 展开全文
递归算法(英语:recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题,因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环,因此在很多函数编程语言(如Scheme)中习惯用递归来实现循环。
信息
外文名
recursive algorithm
特    点
递归就是在过程或函数里调用自身
实现过程
一般通过函数或子过程来实现
中文名
递归算法
属    性
计算机算法
递归算法递归程序
在支持自调用的编程语言中,递归可以通过简单的函数调用来完成,如计算阶乘的程序在数学上可以定义为: 这一程序在Scheme语言中可以写作:即使一个编程语言不支持自调用,如果在这语言中函数是第一类对象(即可以在运行期创建并作为变量处理),递归可以通过不动点组合子(英语:Fixed-point combinator)来产生。以下Scheme程序没有用到自调用,但是利用了一个叫做Z 算子(英语:Z combinator)的不动点组合子,因此同样能达到递归的目的。这一程序思路是,既然在这里函数不能调用其自身,我们可以用 Z 组合子应用(application)这个函数后得到的函数再应用需计算的参数。尾部递归是指递归函数在调用自身后直接传回其值,而不对其再加运算。尾部递归与循环是等价的,而且在一些语言(如Scheme中)可以被优化为循环指令。 因此,在这些语言中尾部递归不会占用调用堆栈空间。以下Scheme程序同样计算一个数字的阶乘,但是使用尾部递归: [1] 
收起全文
精华内容
下载资源
问答
  • 递归算法

    2019-04-01 15:58:22
     递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。 递归算法解决问题的特点:  (1) 递归就是在过程或函数里...

     

    在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法。
      递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解。
    递归算法解决问题的特点:
      (1) 递归就是在过程或函数里调用自身。
      (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
      (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
      (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。在实际编程中尤其要注意栈溢出问题。

      借助递归方法,我们可以把一个相对复杂的问题转化为一个与原问题相似的规模较小的问题来求解,递归方法只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。但在带来便捷的同时,也会有一些缺点,也即:通常用递归方法的运行效率不高。

    1、 Fibonacci数列

    提到递归,我们可能会想到的一个实例便是斐波那契数列。斐波那契数列就是如下的数列:

      0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …,总之,就是第N(N > 2)个数等于第(N - 1)个数和(N - 2)个数的和。用递归算法实现如下:

    public static Integer fibonacci(int i) {
        if (i == 0) {
            return 0;
        }
        if (i == 1) {
            return 1;
        }
        if (i < 0) {
            return -1;
        }
        return fibonacci(i - 1) + fibonacci(i - 2);
    }

    2、阶乘 

    还有就是求一个数的阶乘 n!,也会用到递归,这个比较简单,直接给出实现代码,如图:

    public static Integer Factorial(int i) {
        if (i == 0) {
            return 1;
        }
        return i * Factorial(i - 1);
    }
    public static void main(String[] args) {
        System.out.println(fibonacci(6)); // 8
        System.out.println(Factorial(6)); // 720
    }

    斐波那契数列第6个数是8 ,6的阶乘是720

     3 、汉诺塔问题

     汉诺塔是根据一个传说形成的数学问题:

            汉诺塔示意图(图片来自网络)

     有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
      1、每次只能移动一个圆盘;
      2、大盘不能叠在小盘上面。
      提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。
      问:如何移?最少要移动多少次?

    public class Demo {
        public static void main(String[] args) {
            hannoi(3, "A", "B", "C");
        }
    
        public static void hannoi(int n, String from, String buffer, String to) {
            if (n == 1) {
                System.out.println("Move disk " + n + " from " + from + " to " + to);
            } else {
                hannoi(n - 1, from, to, buffer);
                System.out.println(("Move disk " + n + " from " + from + " to " + to));
                hannoi(n - 1, buffer, from, to);
            }
        }
    }
    控制台输出移动方法:

    Move disk 1 from A to C
    Move disk 2 from A to B
    Move disk 1 from C to B
    Move disk 3 from A to C
    Move disk 1 from B to A
    Move disk 2 from B to C
    Move disk 1 from A to C
     

    展开全文
  • 递归算法转换为非递归算法

    千次阅读 2019-04-24 17:40:07
    对于某些复杂问题(例如hanio塔问题),递归算法是一种自然且合乎逻辑的解决问题的方式,但是递归算法的执行效率通常比较差。因此,在求解某些问题时,常采用递归算法来分析问题,用非递归算法来求解问题...

    转 自 : https://blog.csdn.net/fbz123456/article/details/50959412  
     

    递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题),递归算法是一种自然且合乎逻辑的解决问题的方式,但是递归算法的执行效率通常比较差。因此,在求解某些问题时,常采用递归算法来分析问题,用非递归算法来求解问题;另外,有些程序设计语言不支持递归,这就需要把递归算法转换为非递归算法。
        将递归算法转换为非递归算法有两种方法,一种是直接求值(迭代/循环),不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转换法,下面分别讨论这两种方法。

    1. 直接转换法
    直接转换法通常用来消除尾递归和单向递归,将递归结构用循环结构来替代。
    单向递归:简单的说是指递归的过程总是朝着一个方向进行,如果函数1调用了函数2,而函数2又调用了函数1,则这种情况不属于单向递归。斐波那契数列的递归求解可转用一个迭代法实现。

    斐波那契数列的递归求解:

    int Fib(int n) {
    if(n <= 1) return n;
    else return Fib(n - 1) + Fib(n - 2);
    }

    转化为迭代求解:

    int Fib(int n) {
    if(n <= 1) return n;
    int twoBack = 0;
    int oneBack = 1;
    int cur;
    for(int i = 2;i < = n; i++) {
       cur = twoBack + oneBack;
    twoBack = oneBack;
       oneBack = cur;
    }
    return cur;
    }

    尾递归函数是以递归调用结尾的函数,是单向递归的特例。它的递归调用语句只有一个,而且是放在过程的最后。当递归调用返回时,返回到上一层递归调用语句的下一语句,而这个位置正好是程序的结尾,因此递归工作栈中可以不保存返回地址;除了返回值和引用值外,其他参数和局部变量都不再需要,因此可以不用栈,直接采用循环写出非递归过程。

    阶乘函数就不是一个尾递归。因为在它收到递归调用的结果后,必须在返回调用前再做一次乘法运算。但是阶乘函数可以转化成一个尾递归函数,例:

    阶乘的递归求解:

    int factorial(int n)

    {
    if(n == 0) return 1;
    else

         {
    int val = factorial(n - 1);
    return n * val;
    }
    }

    转化为尾递归求解:

    int factorial(int acc, int x)

     { //acc传的值为1。
    if(x <= 1) return acc;
    else

         return factorial(x * acc, x - 1);
    }

    尾递归的重要性在于当进行尾递归调用时,调用者的返回位置不需要被存在调用栈里。当递归调用返回时,它直接分支到先前已保存的返回地址。因此,在支持尾递归优化的编译器上,尾递归在时间和空间上都比较划算。迭代算法需要一个临时变量,这无疑导致了程序的可读性降低,迭代函数不像递归函数那样需要考虑函数调用的支出,而且对一个线程来说可用的栈空间通常比可用的堆空间要少得多,而递归算法则相对迭代算法需要更多的栈空间!

    2. 间接转换法
    该方法使用栈保存中间结果,一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下:

    将初始状态s0进栈
    while (栈不为空)
    {
    退栈,将栈顶元素赋给s;
    if (s是要找的结果) 返回;
    else {
    寻找到s的相关状态s1;
    将s1进栈
    }
    }

    间接转换法在数据结构中有较多实例,如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等,请读者参考主教材中相关内容。
     

    展开全文
  • 递归算法向非递归算法转换 递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题),递归算法是一种自然且合乎逻辑的解决问题的方式,但是递归算法的执行...

    递归算法向非递归算法转换

    递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题),递归算法是一种自然且合乎逻辑的解决问题的方式,但是递归算法的执行效率通常比较差。因此,在求解某些问题时,常采用递归算法来分析问题,用非递归算法来求解问题;另外,有些程序设计语言不支持递归,这就需要把递归算法转换为非递归算法。

        将递归算法转换为非递归算法有两种方法,一种是直接求值,不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转换法,下面分别讨论这两种方法。

    1. 直接转换法

    直接转换法通常用来消除尾递归和单向递归,将递归结构用循环结构来替代。

    尾递归是指在递归算法中,递归调用语句只有一个,而且是处在算法的最后。例如求阶乘的递归算法:

    long fact(int n)

    {

      if (n==0) return 1;

      else return n*fact(n-1);

    }

    当递归调用返回时,是返回到上一层递归调用的下一条语句,而这个返回位置正好是算法的结束处,所以,不必利用栈来保存返回信息。对于尾递归形式的递归算法,可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法:

    long fact(int n)

    {

      int s=0;

      for (int i=1; i<=n;i++)

      s=s*i; //s保存中间结果

      return s;

    }

    单向递归是指递归算法中虽然有多处递归调用语句,但各递归调用语句的参数之间没有关系,并且这些递归调用语句都处在递归算法的最后。显然,尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下:

    int f(int n)

    {

      if (n= =1 | | n= =0) return 1;

      else return f(n-1)+f(n-2);

    }

    对于单向递归,可以设置一些变量保存中间结构,将递归结构用循环结构来替代。例如求斐波那契数列的算法中用s1s2保存中间的计算结果,非递归函数如下:

    int f(int n)

    {

      int i, s;

      int s1=1, s2=1;

      for (i=3; i<=n; ++i)

            {

             s=s1+s2;

             s2=s1; // 保存f(n-2)的值

             s1=s; //保存f(n-1)的值

      }

      return s;

    }

    2. 间接转换法

    该方法使用栈保存中间结果,一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下:

    将初始状态s0进栈

    while (栈不为空)

    {

      退栈,将栈顶元素赋给s;

      if (s是要找的结果) 返回;

      else

            {

          寻找到s的相关状态s1;

          s1进栈

      }

    }

    间接转换法在数据结构中有较多实例,如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等。

    使用非递归方式实现递归问题的算法程序,不仅可以节省存储空间,而且可以极大地提高算法程序的执行效率。本文将递归问题分成简单递归问题和复杂递归问题;简单递归问题的非递归实现采用递推技术加以求解,复杂递归问题则根据问题求解的特点采用两类非递归实现算法,使用栈加以实现。

    http://wenku.baidu.com/view/0c2409c55fbfc77da269b1c8.html

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 66,267
精华内容 26,506
关键字:

递归算法