递归和递归常见的例子分析

Recursive

Posted by S.L on September 8, 2019

递归算法对于计算机相关领域的同学并不默认,它以实现代码简洁著称,但同时它的可读性又比较差,让人又爱又恨,本文对递归相关的东西做一个小结。

递归的一般模式

stackoverflow上有人总结了一个模型,我觉得可以很好的说明递归程序设计的一般模式:

Result M(Problem prob)
{
    if (<problem can be solved easily>)
        return <easy solution>;
    // The problem cannot be solved easily.
    Problem smaller1 = <reduce problem to smaller problem>
    Result result1 = M(smaller1);
    Problem smaller2 = <reduce problem to smaller problem>
    Result result2 = M(smaller2);
    ...
    Result finalResult = <combine all results of smaller problem to solve large problem>
    return finalResult;
}

顺便给了一个求树的高度的例子:

int Depth(Tree tree)
{
    // Start with the trivial case. Is the tree empty?
    if (tree.IsEmpty) return 0;
    // The tree is not empty. 
    // Reduce the problem to two smaller problems and solve them:
    int depthLeft = Depth(tree.Left);
    int depthRight = Depth(tree.Right);
    // Now combine the two solutions to solve the larger problem.
    return Math.Max(depthLeft, depthRight) + 1;
}

递归程序的特点

所有的递归程序都具有以下特点:

  • 这些方法使用if-else或switch语句来引导不同的情况
  • 一个或多个基础情况(最简单的情况)用来终止递归
  • 每次递归都会简化原始问题,让它不断接近基础情况,直到它变成基础情况(最小问题)为止
  • 一个复杂的问题的解决需要依赖一个或多个子问题的解决,并根据子问题的解决结果来决定当前问题如何解决

函数调用、理解递归

对于程序,编译器会对其分配一段内存,在逻辑上可以分为代码段,数据段,堆,栈:

  • 代码段:保存程序文本,指令指针EIP就是指向代码段,可读可执行不可写
  • 数据段:保存初始化的全局变量和静态变量,可读可写不可执行
  • BSS:未初始化的全局变量和静态变量
  • 堆(Heap):动态分配内存,向地址增大的方向增长,可读可写可执行
  • 栈(Stack):存放局部变量,函数参数,当前状态,函数调用信息等,向地址减小的方向增长,可读可写可执行

对于递归来说,栈的概念非常重要:先进后出,如果当前函数执行到需要依赖其他函数的返回结果时,会被先压入栈,等下一层函数返回结果后,再被弹出栈,继续运行。

经典递归问题

1、回文字符串判断

验证指定的字符串是否为回文,如「abcdedcba」

迭代

for循环的做法:依次判断字符串的收尾,start和end索引位置的字符是否相同,相同则start++,end–,依次判断,直到start==end或start>end,证明是回文。 这里不做赘述。

递归

递归的做法:跳出条件start>=end时直接返回true,否则判断start和end位置的字符,再递归调用方法前注意调整两个index的位置。

public static boolean isPalindrome( String str ){
    //重载调用,并且左边参数从下标0开始,右边参数从字符串尾端的位置开始
    return isPalindrome( str, 0, str.length() - 1 );
}

public static boolean isPalindrome( String str, int beginIndex, int tailIndex ){
    if( tailIndex <= beginIndex ){
        //如果到达中心点,表明前面的所有字符都两端相等,那么就返回true
        return true;
    } else if( str.charAt( beginIndex ) != str.charAt( tailIndex ) ){
        //如果有字符串不相等,那么就返回false
        return false;
    } else{
        //否则,表明并没有到达中心点,但这次下标的两个字符相等,继续判断下一个
        //左边下标指向后移,右边下标指向前移
        return isPalindrome( str, beginIndex+1, tailIndex-1 );
    }
}

这里使用了递归辅助方法,通俗来说,递归辅助方法就是通过对方法的重载,给原方法参数基础上增加额外的参数,使在调用的时候通过重载达到我们的需要。

如果不使用递归辅助方法,使用一个参数作为函数声明,则代码如下:

public static boolean isPalindrome(String str) {
    if ( str.charAt(0) != str.charAt(str.length() - 1) ) {
        return false;
    }

    if (str.length() <= 1) {
        return true;
    }
    
    return isPalindrome(str.substring(1, str.length() - 1));//切割两端,将子串递归调用
}

方法参数省去了两个独立的 index 变量,使得计算完全依赖于参数 str ,以及它的长度,这样做的一个坏处是,在 JavaString#substring() 方法会每次生成一个新的字符串,一共需要对比 len/2 次,即一共产生 len/2 个子字符串,当原始字符串较长时,会浪费很多内存空间。

2、Palindrome Number

这里和1的区别是数字,不能使用字符串相关的特性,如下标来计算,只能用数学计算。

通过取整和取余操作获取整数中对应的数字进行比较。

举个例子:1221 这个数字。

通过计算 1221 / 1000, 得首位1

通过计算 1221 % 10, 可得末位 1

进行比较

再将 22 取出来继续比较

递归
public static boolean isPalindrome(int x) {
    int n = 0, div = 1;
    while(x / div >= 1) {
        div *= 10;
        n ++;
    }
    return isPalindrome(x, n);
}

public static boolean isPalindrome(int x, int len) {
    // 边界判断
    if (x < 0) return false;
    if (len == 1 || len == 0) return true;

    int div = 1;
    int newLen = len - 2;
    while (--len > 0) div *= 10;
    int left = x / div;
    int right = x % 10;
    if (left != right) return false;
    x = (x % div) / 10;
    return isPalindrome(x, newLen);
}
非递归

使用while 进行迭代,每一轮都比较当前数字的 的两个数值,不相同直接返回 false

public static boolean isPalindrome(int x) {
    // 边界判断
    if (x < 0) return false;
    int div = 1;
    // 需要首先算出该数字除了最高位外的位数包含几个0
    while (x / div >= 10) div *= 10;
    while (x > 0) {
        int left = x / div;
        int right = x % 10;
        if (left != right) return false; // 短路
        // x % div,同位数之间的数字取模,余数是去掉最高同位数的数字的后面的部分
        // 即 983 % 100 = 83
        x = (x % div) / 10;
        div /= 100; // 收尾比较完毕后下一轮比较,需要去掉两个0
    }
    return true;
}

下面这种写法只能在全部转换完毕后才能知道是否是回文,因为它是按照从尾部开始往前构建一个反转数字的:

boolean isPalindrome(int x) {
    if(x < 0)   return false;
    int r = 0, t;
    t = x;
    while(t != 0)
    {
        r = r * 10 + t % 10;
        t /= 10;
    }
    return r == x;

}

3、Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321 Example2: x = -123, return -321

思路1:用long

为了防止溢出,可以考虑使用 long 进行计算中间结果:

int reverse(int x) {
    long tmp = 0;
    while(x != 0)
    {
        tmp *= 10;
        tmp += x % 10; /* 这两行可以简写成 tmp = tmp * 10 + x % 10 */
        if(tmp > INT_MAX || tmp < INT_MIN)
            return 0;
        x /= 10;
    }
    return tmp;
}

思路2:变化前后对比

如果溢出了,那溢出后的值做反向操作会和之前的值不一样的,可以直接校验得出结论:

public int reverse(int x) { 
    int result = 0;
    while (x != 0)
    {
        int tail = x % 10;
        // 注意这一步可能溢出
        int newResult = result * 10 + tail;
        // 将上一步的算式反向计算一遍看是否能得到和result相同的结果,不可以就是溢出了
        if ((newResult - tail) / 10 != result)
        { 
            return 0; 
        }
        result = newResult;
        x = x / 10;
    }

    return result;
}

思路3:提前停止操作

如果当前的数已经>INT_MAX/10 , 那么再做一次操作,必然溢出。反之也是一样,如果当前的数已经 <INT_MIN/10 ,那么再做一次操作也必然会溢出。

int reverse(int n)
    {
        int result = 0;

        while (n != 0)
        {
            if (result > INT_MAX / 10
                    || ((result == INT_MAX / 10) && (n % 10 > INT_MAX % 10)))
            {
                result = 0;
                break;
            }
            if (result < INT_MIN / 10
                    || ((result == INT_MIN/ 10) && (n % 10 < INT_MIN % 10)))
            {
                result = 0;
                break;
            }
            result = result * 10 + n % 10;
            n = n / 10;
        }


        return result;
    }

4、Symmetric Tree

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

 1

/ \

2 2

/ \ / \

3 4 4 3

例如,二叉树 [1,2,2,nil,4,4,nil] 也是对称的。

 1

/ \

2 2

\ / 

4 4  用递归做比较简单:一棵树是对称的等价于它的左子树和右子树两棵树是对称的,问题就转变为判断两棵树是否对称。 ```java public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
// 把问题变成判断两棵树是否是对称的
return isSym(root.left, root.right); } //判断的是根节点为r1和r2的两棵树是否是对称的 public boolean isSym(TreeNode r1, TreeNode r2){
if(r1 == null && r2 == null) return true;
if(r1 == null || r2 == null) return false;
// 这两棵树是对称需要满足的条件:
// 1.俩根节点相等。 2.树1的左子树和树2的右子树,树2的左子树和树1的右子树都得是对称的
return r1.val == r2.val && isSym(r1.left, r2.right) 
                    && isSym(r1.right, r2.left); } ```

本文首次发布于 S.L’s Blog, 作者 @stuartlau , 转载请保留原文链接.