递归

发表于 | 分类于

任何循环都可以改为递归，关键是发现逻辑“相似性”和递归出口。
有些语言没有循环只有递归，如lisp和clojure。拓展尾递归。

数组求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package bluebridgecup;

public class A01_SumArray {

    public static int f1(int[] arr)
    {
        int sum = 0;
        for (int i = 0; i < arr.length; i++)
        {
            sum += arr[i];
        }
        return sum;
    }

    //**************************线性递归**************************
    public static int f2(int[] arr,int start)
    {
        if (start == arr.length) //递归出口
            return 0;
        return arr[start] + f2(arr,start+1);
    }


    public static int f3_2(int[] arr,int end)
    {
        if (end < 0) //递归出口
            return 0;
        return f3_2(arr,end-1) + arr[end];
    }

    //**************************二分递归**************************
    public static int f4(int[] arr,int start,int end)
    {
        if (start > end) return 0;//递归出口
        int mid = (start + end)/2;
        return f4(arr,start,mid-1) + arr[mid] + f4(arr,mid+1,end);//todo 不如下面的方式
    }

    public static int f5(int[] arr,int start,int end)
    {
        if (start == end) return arr[start];//递归出口
        int mid = (start + end)/2;
        return f5(arr,start,mid) + f5(arr,mid+1,end);//注意分为mid    mid+1
    }

    public static void main(String[] args)
    {
//        int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10};
//        System.out.println(f1(arr));

//        System.out.println(f2(arr,0));
//        System.out.println(f3_2(arr,arr.length - 1));

//        System.out.println(f4(arr,0,arr.length - 1));
//        System.out.println(f5(arr,0,arr.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
24
25
26
27
28
29
30
package bluebridgecup;

public class A02_PrintArray {

    private static void f1(int n) {
        if (n > 0) f1(n - 1);
        System.out.println(n);

    }

    private static void f2(int start, int end) {
        if (start > end)return;
        System.out.println(start);
        f2(start+1,end);
    }

    public static void f_arr(int[] arr,int start){
        if (start > arr.length - 1)return;
        System.out.println(arr[start]);
        f_arr(arr,start+1);
    }

    public static void main(String[] args){
//        f1(10);
//        f2(0,10);

//        int[] arr = new int[]{1,2,3,4,5,6,7,8,9,10};
//        fa(arr,0);
    }
}

字符串是否相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package bluebridgecup;

public class A03_IsSameString {


    private static boolean isSameString2(String s1, String s2) {
        if (s1.length() != s2.length()) return false;//******边界********
        if (s1.length() == 0) return true;//******边界********

//        if (s1.charAt(0) != s2.charAt(0)) return false;
        if (s1.charAt(0) == s2.charAt(0)) return true;
        return isSameString2(s1.substring(1),s2.substring(1));
    }

    public static boolean isSameString1(String s1,String s2){
        return s1.equals(s2);
    }


    public static void main(String[] args) {
//        String s1 = "abc";
//        String s2 = "abcd";
//        System.out.println(isSameString1(s1,s2));
//        System.out.println(isSameString2(s1,s2));
    }
}

求阶乘

1
2
3
4
5
6
7
8
9
10
11
12
package bluebridgecup;

public class A04_FactorialOfN {
    public static void main(String[] args) {
        System.out.println(helper(3));
    }

    private static int helper(int n) {
        if (n > 0)return n * helper(n - 1);
        return 1;
    }
}

求n个不同元素的全排列*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package bluebridgecup;

/**
 * 求n个不同元素的全排列
 *
 * 回溯问题，用于八皇后和迷宫问题
 * 如果包含重复元素怎么办?
 * 罗列出每一种可能用什么方法?动态规划怎么实现
 *
 *
 * R的全排列可归纳定义如下：
 * 当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；
 * 当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。
 * 实现思想：将整组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。
 */
public class A05_FullPermutation {
    public static void main(String[] args) {
        char[] chars = "ABC".toCharArray();
        helper(chars,0);
    }

    //k:当前的交换位置(关注点),与其后的元素交换
    private static void helper(char[] chars,int k) {
        if (k == chars.length){
            for (char c:chars) System.out.print(c +" ");
            System.out.println();
        }
        for (int i = k; i < chars.length; i++) {
            {char t = chars[k];chars[k] = chars[i];chars[i] = t;}//试探
            helper(chars,k + 1);
            {char t = chars[k];chars[k] = chars[i];chars[i] = t;}//回溯
        }
    }
}

在n个求中，任意取出m个，求有多少种不同取法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package bluebridgecup;

/**
 * 在n个求中，任意取出m个，求有多少种不同取法
 */
public class A06_GraspBall {
    //从n个取m个
    public static void main(String[] args) {
        int k = helper(5,3);
        System.out.println(k);
    }

    private static int helper(int n, int m) {
        if (n < m) return 0;
        if (n == m) return 1;
        if (m == 0) return 1;
        return helper(n - 1,m - 1) + helper(n - 1,m);//n个里有个特殊球x，取法划分，包不包含x
    }
}

求最长公共子序列的长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package bluebridgecup;

public class A07_MaxSequence {
    public static void main(String[] args) {
        String s1 = "abc";
        String s2 = "xbacd";
        int x = helper(s1,s2);
        System.out.println(x);
    }

    private static int helper(String s1, String s2) {
        if (s1.length() == 0 || s2.length() == 0)return 0;
        if (s1.charAt(0) == s2.charAt(0)){
            return 1 + helper(s1.substring(1),s2.substring(1));
        } else {
            return Math.max(helper(s1,s2.substring(1)),helper(s1.substring(1),s2));
        }
    }
}

翻转字符串

1
2
3
4
5
6
7
8
9
10
11
12
package bluebridgecup;

public class A08_Reverse {
    public static void main(String[] args) {
        System.out.println(helper_str("12345"));;
    }

    private static String helper_str(String s) {
        if (s.length() == 0)return "";
        return helper_str(s.substring(1))+s.charAt(0);
    }
}

杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package bluebridgecup;

/**
 * 1
 * 1 1
 * 1 2 1
 * 1 3 3 1
 * 1 4 6 4 1
 * 1 5 10 10 5 1
 *
 * 计算第m层，第n个系数，m和n都从0开始
 */
public class A09_YangTriangle {

    public static void main(String[] args) {
        int level = 5;
        for (int i = 0; i <= level; i++) {
            System.out.print(helper(level,i) +" ");
        }
        System.out.println();
    }

    //m层第n个元素
    private static int helper(int m,int n){
        if (n == 0)return 1;
        if (m == n)return 1;
        return helper(m - 1,n) + helper(m - 1,n - 1);
    }
}

m个a,n个b 可以有多少种组合

1
2
3
4
5
6
7
8
9
10
11
12
package bluebridgecup;
// m个a,n个b 可以有多少种组合
public class A10_MN_sort {
    public static void main(String[] args) {
        System.out.println(helper(3,2));
    }

    private static int helper(int m, int n) {
        if (m == 0 || n == 0)return 1;
        return helper(m - 1,n) + helper(m,n - 1);
    }
}

split 6

upload successful

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package bluebridgecup;

public class A11_Split_6 {

    public static void main(String[] args) {
        int[] a = new int[100];//做缓冲
        helper(3,a,0);
    }

    //对n进行加法划分
    // a:缓冲
    // k:当前的位置
    private static void helper(int n,int[] a,int k) {
        if (n <= 0){
            for(int i=0;i < k;i++)System.out.printf(a[i] + " ");
            System.out.println();
            return;
        }
        //6
        //5...f(1)
        //4...f(2)
        for (int i = n; i > 0; i--) {
            if (k > 0 && i > a[k - 1])continue;//a[k - 1]表示前一项   ;   后一项 > 前一项
            a[k] = i;
            helper(n - i,a,k + 1);
        }
    }
}

ErrorSum

upload successful

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package bluebridgecup;

public class A12_ErrorSum {
    public static void main(String[] args) {
        int sum = 6;
        int[] a = {3,2,4,3,1};
        boolean[] b = new boolean[a.length];//表示a对应项是否选取
        helper(sum,a,0,0,b);
    }

    //error_sum:有错误的和
    //a：明细
    //k:当前处理的位置
    //cur_sum:前边元素的累加和
    //b:记录取舍
    private static void helper(int error_sum, int[] a, int k, int cur_sum, boolean[] b) {
        if (cur_sum > error_sum)return;
        if (error_sum == cur_sum){
            for(int i = 0;i < b.length;i++) if (b[i] == true)System.out.printf(a[i]+" ");
            System.out.println();
            return;
        }
        if (k >= a.length)return;
        b[k] = false;
        helper(error_sum,a,k + 1,cur_sum,b);
        b[k] = true;
        cur_sum += a[k];
        helper(error_sum,a,k + 1,cur_sum,b);
        b[k] = false;//回溯！！！！！
    }
}

打印二叉树从根节点到叶子节点的所有路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package bluebridgecup;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
//打印二叉树从根节点到叶子节点的所有路径
public class A13_BSTTreePath {

    List<String> res = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null)return new ArrayList<>();
        LinkedList<Integer> list = new LinkedList<>();
        helper(root,list);
        return res;
    }

    private void helper(TreeNode node,LinkedList<Integer> list) {
        if (node == null) return;
        list.add(node.val);
        if (node.left == null && node.right == null){
            String s = "";
            for (Integer n:list) {
                if (s.equals("")){
                    s += n+"";
                } else {
                    s = s + "->"+ n;
                }
            }
            res.add(s);
            list.removeLast();//TODO 最后一个节点是叶子节点,继续下一条路线,所以要剔除最后一个
            return;//TODO 该次结束，返回到上一层
        }
        helper(node.left,list);
        helper(node.right,list);
        list.removeLast();//TODO  返回时一定要清除    最后一个节点是最后一个叉的根节点,一定是要排除的,因为这个节点的左右方向都走完了
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}

汉诺塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package bluebridgecup;

public class A14_Hanoi {
    public static void main(String[] args) {
        hanoi(2,"1","2","3");
    }

    public static void hanoi(int n,String start,String middle,String end){
        if (n <= 1){
            System.out.println(start+"-->"+end);
        } else {
            hanoi(n -1,start,end,middle);
            System.out.println(start+"-->"+end);
            hanoi(n - 1,middle,start,end);
        }
    }
}

遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package bluebridgecup;

import java.util.ArrayList;

public class A15_TreeRec {
    /**
     * 中序遍历递归解法
     * （1）如果二叉树为空，空操作。
     * （2）如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树
     */
    public void inOrderRec(TreeNode root){
        if (root == null)return;
        inOrderRec(root.left);
        System.out.println(root.val);
        inOrderRec(root.right);
    }

    /**
     *  分层遍历二叉树（递归）
     *  很少有人会用递归去做level traversal
     *  基本思想是用一个大的ArrayList，里面包含了每一层的ArrayList。
     *  大的ArrayList的size和level有关系
     *
     */
    public static void levelTraversalRec(TreeNode root) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        dfs(root, 0, ret);
        System.out.println(ret);
    }

    private static void dfs(TreeNode root, int level, ArrayList<ArrayList<Integer>> ret){
        if(root == null){
            return;
        }

        // 添加一个新的ArrayList表示新的一层
        if(level >= ret.size()){
            ret.add(new ArrayList<Integer>());
        }

        ret.get(level).add(root.val);   // 把节点添加到表示那一层的ArrayList里
        dfs(root.left, level+1, ret);       // 递归处理下一层的左子树和右子树
        dfs(root.right, level+1, ret);
    }

    /**
     * 求二叉树中的节点个数递归解法： O(n)
     * （1）如果二叉树为空，节点个数为0
     * （2）如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
     */
    public static int getNodeNumRec(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;  //左 右节点加上主节点1为总数
        }
    }



    /**
     * 求二叉树的深度（高度） 递归解法： O(n)
     * （1）如果二叉树为空，二叉树的深度为0
     * （2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1
     *
     *
     *
     maxDepth()
     1. 如果树为空，那么返回0
     2. 否则
     (a) 递归得到左子树的最大高度
     例如，调用maxDepth( tree-> left-subtree )
     (b) 递归得到右子树的最大高度
     例如，调用maxDepth( tree-> right-subtree )
     (c) 对于当前节点，取左右子树高度的最大值并加1。
     max_depth = max(左子树的最大高度, 右子树的最大高度) + 1
     (d) 返回max_depth
     */
    public static int getDepthRec(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int leftDepth = getDepthRec(root.left);
        int rightDepth = getDepthRec(root.right);
        return Math.max(leftDepth, rightDepth) + 1;   // +1是因为根节点已经是一层了,否则root==null直接是0了
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}

翻转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package com.lifeibigdata.offer;

import java.util.Stack;

/**
 * 从尾到头打印链表
 * Created by lifei on 16/11/13.
 */
public class PrintListReverse {
    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);Node n3 = new Node(3);
        Node n4 = new Node(4);Node n5 = new Node(5);
        n1.next = n2;n2.next = n3;n3.next = n4;n4.next = n5;
        printListReverse2(n1);
    }

    static void printListReverse1(Node head){
        Stack<Node> stack = new Stack();
        Node tmpNode = head;
        while (tmpNode != null){
            stack.push(tmpNode);
            tmpNode = tmpNode.next;
        }
        while (!stack.isEmpty()){
            System.out.println(stack.pop().val);
        }
    }

    /**
     * 栈的本质是递归,要实现反过来输出链表,我们访问到一个节点的时候,先递归输出后面的节点,再输入该节点本身,这样链表的输出结果就反过来了
     * @param head
     */
    static void printListReverse2(Node head){
        if (head != null){
            if (head.next != null){
                printListReverse2(head.next);
            }
            System.out.println(head.val);
        }
    }
}