// 第 12 周 – 实践课练习的参考答案
// 运行：java Exercises12.java
public class Exercises12 {

    // E1. 数字和
    static int digitSum(int n) {
        return n < 10 ? n : n % 10 + digitSum(n / 10);
    }

    // E2. 递归求二进制表示（不用栈，由调用栈把顺序逆转！）
    static String toBinary(int n) {
        if (n < 2) return String.valueOf(n);
        return toBinary(n / 2) + (n % 2);
    }

    // E3. 递归求数组的最大值
    static int max(int[] a, int i) {
        if (i == a.length - 1) return a[i];
        return Math.max(a[i], max(a, i + 1));
    }

    // E4. 出现次数
    static int count(int[] a, int i, int x) {
        if (i == a.length) return 0;
        return (a[i] == x ? 1 : 0) + count(a, i + 1, x);
    }

    // E5. 用递归反向输出链表
    static class Node {
        int value;
        Node next;
        Node(int v, Node n) { value = v; next = n; }
    }

    static void printBackward(Node p) {
        if (p == null) return;
        printBackward(p.next);           // 先输出其余部分……
        System.out.print(p.value + " "); // ……然后才输出当前结点
    }

    // E6. 递归求链表长度
    static int length(Node p) { return p == null ? 0 : 1 + length(p.next); }

    // E7. 二项式系数：C(n, k) = C(n−1, k−1) + C(n−1, k)（杨辉三角）
    static long binom(int n, int k) {
        if (k == 0 || k == n) return 1;
        return binom(n - 1, k - 1) + binom(n - 1, k);
    }

    public static void main(String[] args) {
        System.out.println("E1. digitSum(2026) = " + digitSum(2026));
        System.out.println("E2. toBinary(50) = " + toBinary(50));
        System.out.println("E3. max([3,9,2,7]) = " + max(new int[] { 3, 9, 2, 7 }, 0));
        System.out.println("E4. count([1,2,1,1,3], 1) = " + count(new int[] { 1, 2, 1, 1, 3 }, 0, 1));
        Node list = new Node(1, new Node(2, new Node(3, new Node(4, null))));
        System.out.print("E5. printBackward([1,2,3,4]): ");
        printBackward(list);
        System.out.println();
        System.out.println("E6. length = " + length(list));
        System.out.println("E7. binom(5, 2) = " + binom(5, 2) + ", binom(10, 5) = " + binom(10, 5));
    }
}