java - 递归定义解决方案

Question

我正在学习课本上的期末考试。我需要这个问题的答案，因为我无法解决它。

1) 编写函数 multiply(int a, int b) 的递归定义，它接受两个整数并返回它们相乘的结果。

我回答了：

Multiply(a, b) :
0 - if a or b is equal to zero.   (I got -1 here. Reason written: only 1)
a * b - (I didn't know what to write here)

2) 编写一个递归方法，该方法接受一个整数链表并返回其元素的总和。

我的解决方案是：

int sumList(Node<Integer> list) {

    int temp = list.getInfo();

    if(temp == null) {
        return 0;

    } else {
        return temp + sumList(temp.getNext);
    }
}

我修好了，我想：

 public int sumList(Node<Integer> list) {

    Node<Integer> temp = list;

    if(temp == null) {
        return 0;

    } else {
        return temp.getInfo() + sumList(temp.getNext());
    }
}

问题2的解决方案正确吗？

Answer 1

由于这是为了准备考试，我不想给你这样做的代码。相反，我会给你一些想法。

对于第 1 个问题。由于乘法是重复求和，因此您可以在此处将其用作递归的基础。

如果要找到 3 * 4，使用递归计算并返回 4 + 4 + 4。

换句话说，您可以在下面看到一个模式。

4 * 3 = 4 + (4 * 2)

4 * 3 = 4 + 4 + (4 * 1)

Answer 2

A）好吧，你真的需要重新阅读关于递归的那一章。

数学原理是这样的：

http://en.wikipedia.org/wiki/Mathematical_induction

维基百科的文章将引导您完成一项更复杂的任务。

B）不，它根本不会编译。有多个语法错误。

尝试使用 Java 编译器来锻炼您的编程技能。

Answer 3

例如，要获得一个可行的递归解决方案，您需要一个基本案例，a == 0然后通过递归调用自己来努力实现基本案例。

问题 1 的解决方案可能是这样的，它减少了a论点，直到它达到0：

int multiply(int a, int b) {
    if (a == 0 || b == 0) {
        return 0;
    } 
    return b + multiply(a - 1, b);
}

例如，multiply(2, 5)将变为5 + multiply(1, 5)-> 5 + 5 + multiply(0, 5)-> 5 + 5 + 0。

请注意，此特定解决方案不适用于负数，但您明白了。您应该能够轻松地自己添加对此的支持。