php递归乘法技巧_递归乘法算法

根据上图，我们可以知道两个正整数(a和b)的相乘, 实在便是b个a相加，或者a个b相加。

大略的方法便是把a一个一个加起来，或者把b一个一个加起来。
这时时间繁芜度为O(a)或O(b)。

上面的方法有两个地方可以优化：

public int multiplyRecursion(int a, int b){ int smaller = a > b ? b : a; int bigger = a > b ? a : b; return multiply(smaller, bigger);}private int multiply(int smaller, int bigger){ if(smaller == 0) return 0; if(smaller == 1) return bigger; int halfSmaller = smaller / 2; int halfResult = multiply(halfSmaller, bigger); if(smaller % 2 == 0) return halfResult + halfResult; else return halfResult + halfResult + bigger;}

韶光繁芜度：O(lg min(a, b))。