数值自乘（递归与非递归解）

本文主要是介绍数值自乘（递归与非递归解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如果m和n是正整数，那么m^n就是把m连乘n次，这是一个很没效率的方法。其实用分置+递归可以更有效地解决该问题！

首先来看看我最初写的程序吧~

int R_POWER(int m,int n)
{
    if(n==0)
    return 1;
    else if(n==1)
    return m;
    return R_POWER(m,n/2)*R_POWER(m,n-n/2);
}

其中用到的其实是非常朴素的递归方式，无法是将m^n均分成两部分，但是可能会存在奇偶等问题的干扰，所以干脆将两个递归函数的系数分别设为n/2和n-n/2。而递归结束的条件是n==1或n==2。这样其实只要做O(lgn)次乘法就能解决问题了。

不过其实这段代码还是存在缺陷的，它对递归边界条件的判断而且将原函数分治为n/2和n-n/2虽然代码是少写了几行，但是n/2和n-n/2至多差1，最后一行完全可用

    return R_POWER(m,n/2)*R_POWER(m,n/2)*m;//若n为奇数

    return R_POWER(m,n/2)*R_POWER(m,n/2);//若n为偶数数



来代替，用一个变量保存R_POWER（m,n/2）就得到了下面的运行

这篇关于数值自乘（递归与非递归解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---