java - 如何递归地求解程序

Question

我需要有关满足以下引用的程序的帮助:

All integers >= 2 can be factored into the product of only prime numbers. For instance, the number 12 has a prime factorization of 2*2*3, while the number 100 has a prime factorization of 2*2*5*5. We are interested in knowing whether an input integer has a prime factorization that only has 2s and 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

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