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

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

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

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

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

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 است.