【算法 - 方法】(2)递归

【算法 - 方法】(2)递归

一、递归

程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

1.定义

递归,就是在运行的过程中调用自己。
构成递归需具备的条件:

  1. 子问题须与原始问题为同样的事,且更为简单;
  2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理。

2.应用

2.1 场景

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

  • (1)数据的定义是按递归定义的。(Fibonacci函数)
  • (2)问题解法按递归算法实现。(这类问题虽则本身没有明显的递归结构,但用递归求解比迭代求解更简单,如Hanoi问题。)
  • (3)数据的结构形式是按递归定义的。(如二叉树、广义表等,由于结构本身固有的递归特性,则它们的操作可递归地描述。)
2.2 缺点

递归的缺点:

递归算法解题相对常用的算法如普通循环等,运行效率较低。因此,应该尽量避免使用递归,除非没有更好的算法或者某种特定情况,递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

2.3 设计递归算法

如何设计递归算法

  1. 确定递归公式
  2. 确定边界(终了)条件

1.递归公式

  • 找重复(子问题)
  • 找重复中的变化量(参数,递归公式)

2.确定边界

  • 找参数变化趋势(终止条件,设计出口)

二、递归练习

小技巧:当前f(n)想象成当前需要解决的小问题,将f(n-1)想象成其他函数。

1.递归基础

求n的阶乘

    /**
     * 求n的阶乘
     * 找重复:找出子问题(f(n)只做一小部分,另外的给别的函数做)
     * 找变化(递归公式):n-1
     * 找边界(出口):n==1
     *
     * 理解:
     * 尽量分解成规模更小的子问题。
     * 假设f(n)是n,则f(n-1)就是n-1
     */
    static int f(int n) {
        if (n==1) return 1;
        return n*f(n-1);
    }

打印i到j

    /**
     * 打印i到j
     * 找重复:找出子问题(f(n)只做一小部分(只打印第一个数),另外的给别的函数做)
     * 找变化:i+1
     * 找出口:i==j
     */
    static void f2(int i, int j) {
        if (i==j) return;
        System.out.println(i);
        f2(i+1, j);
    }

对数组中所有元素求和

    /**
     * 对数组中所有元素求和
     * 找重复:找出子问题(f(n)只做一小部分(只求第一个元素),剩下的留给别的函数做)
     * 找变化:i+1
     * 找出口:i==arr.length
     *
     * 注意:当参数不足构成递归时,需要手动添加变化参数.
     */
    static int f3(int[] arr, int i) {
        if (i==arr.length) return 0;
        return arr[i]+f3(arr,i+1);
    }

反转字符串

测试反转字符串代码:

    public static void main(String[] args) {
        System.out.println(f4("12345", 0));

        String s = "12345";
        System.out.println(f4_2(s, s.length()-1));
    }
    /**
     * 反转字符串
     * 递归公式:f(n)只反转第一个,剩下的交给f(n-1)。
     * 出口:i==s.length()
     */
    static String f4(String s, int i) {
        if (i==s.length()) return "";
        return f4(s, i+1) + s.charAt(i);
    }

    /**
     * 反转字符串2
     * 递归公式:f(n)只反转最后一个,剩下的交给f(n-1)。
     * 出口:i==-1
     */
    static String f4_2(String s, int i) {
        if (i == -1) return "";
        return s.charAt(i) + f4_2(s, i-1);
    }

2.多分枝递归

求斐波那契数第n项

使用递归求斐波那契第n项会非常慢,时间复杂度为O(2n),这里只是学习递归。

    /**
     * 求斐波那契数第n项
     * 递归公式:当前f(n)仅把f(n-1)和f(n-2)加起来,剩下的交给别的函数做。
     * 出口:i==1 || i==2
     *
     * 求斐波那契f(n)会有多个分支,所以叫做多分枝递归。
     * 例如,求f(5)时:f(5) = f(4)+f(3),
     * 先算左边的f(4) = f(3)+f(2),再算f(4)左边的f(3):f(3)=f(2)+f(1),再算f(3)左边的f(2)。
     * 此时单单只算了最左边的递归,而且还有右边的很多分支没有计算(还有很多分支没写出来,可以自己列举一下)。
     *
     * 并且,该问题求解时,会有很多分支重复求解,很浪费资源。
     */
    static int f(int n) {
        if (n==1 || n==2) return 1;
        return f(n-1) + f(n - 2);
    }

其他

参考

百度百科 - 递归:https://baike.baidu.com/item/%E9%80%92%E5%BD%92/1740695

知乎 - 对于递归有没有什么好的理解方法?:https://www.zhihu.com/question/31412436

算法很美-Java版本:https://www.bilibili.com/video/av75374427?p=10