محاسبه‌ی توان به شیوه‌ی بازگشتی

یکی از مسئله‌هایی که به کمک الگوریتم‌های بازگشتی حل می‌شود، محاسبه‌ی توان است.شیوه‌های مختلفی برای پیاده‌سازی بازگشتی توان وجود دارد.

الگوریتم اول

• ساده‌ترین الگوریتم بازگشتی برای محاسبه‌ی توان، آن است که ابتدا $a^n/a$ را به صورت بازگشتی به‌دست آوریم و سپس آن را در a ضرب کنیم تا مقدار $a^n$ به‌دست آید.
• پیاده سازی این الگوریتم در زیر آمده است : (مشخص است که زمان اجرای این الگوریتم O(n) است.)

int power(double a, int n) {
    if (n == 0)
        return 1;
    return power(a,n-1)*a;
}

الگوریتم دوم

• ایده‌ی الگوریتم دوم آن است که، برای محاسبه‌ی $2^k\times2$ نیازی نیست که همه‌ی توان‌های کوچکتر از $2k$ را حساب کنیم. می‌توان ابتدا $2^k$ را محاسبه کرد و سپس آن را به توان ۲ رساند.
• پیاده‌سازی این الگوریتم:

int power (double a, int n) {
    if (n == 0)
        return 1;
    if (n % 2 == 0)
        return pow (power(a,n/2),2);
    else
        return a*pow (power(a,n/2),2);

در هر مرحله از بازگشت، مقدار توان نصف می‌شود و بنابراین زمان کل اجرای الگوریتم، (O(log n است.