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

1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}

1
2
3
4
5
6
7
8
9
10
11
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 );
    }
}

1
2
3
4
5
6
7
8
9
10
11
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));//切割两端，将子串递归调用
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
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;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}