如何递归求解程序

Question

我需要帮助的程序，满足以下报价：

所有整数>= 2只能被分解为素数的乘积。例如，数字12的素数因式分解为2*2*3，而数字100的素数分解为2*2*5*5。我们想知道输入整数是否有一个只有2s和3s的素数因式分解。

我想我需要更多的基本条件和一个捕获所有递归调用。

现行(未完成)守则：

    public static boolean hasFactors2and3(int number) throws IllegalArgumentException{
        if (number < 2) throw new IllegalArgumentException("Number is less than 2");
        if (number >= 2 && number < 5) return true; // because for all these numbers it works
        if (number % 2 == 0) return hasFactors2and3(number /= 2);
        if (number % 3 == 0) return hasFactors2and3(number /= 3);

    }

任何帮助都是非常感谢的！

Answer 1

您需要一个递归的解决方案。我不会给你这个的。相反，我将在伪代码中给出一个非递归的解决方案，并由您将其转换为递归解决方案。

function hasFactors2and3(number)

  // Deal with negatives, 0, 1.
  if (number < 2)
    return false
  endif

  // Remove factors of 2.
  while (number MOD 2 == 0)
    number <- number / 2
  endwhile

  // Remove factors of 3.
  while (number MOD 3 == 0)
    number <- number / 3
  endwhile

  // See what factors are left after removing all 2s and 3s.
  return number == 1

end function

提示:研究如何使用循环删除尾递归，然后逆转过程。