c - 在 'while loop' 中实现印度算法。我做错了什么？

Question

我被告知要在 while 循环内实现函数而不是递归函数。到目前为止，我总是得到错误的答案。任何关于我在哪里犯错的指标都将不胜感激。我正在尝试计算 2^12，但到目前为止，每当我运行程序时，它都会给我 4。最初的问题然后我创建了这个线程已经解决了。但是我有一个与前一个问题相关的新问题，但需要一种不同的方法

#include <stdio.h>

double powerloop(double x, int y, double help)
{
   while(y!=0)
   {
     if((y%2)==0)
     {
        x=x*x;
        y=y/2;
     }

     if((y%2)==1)
     {
        help=help*x;
        x=x*x;
        y=(y-1)/2;
     }

     if(y==1)
     {
       x=x*help;
     }

     return x;
  }
}

int main(void){
     printf("Using powerloop to calculate 2^12: %f \n", powerloop(2, 12, 1));
     return 0;
}

Answer 1

两个问题:

1.下面的测试是错误的:

if(y & 2 == 0)

你想要

if((y % 2) == 0)

模 % 运算符与对 2 进行“按位与”运算并不完全相同。

2.初始行

 double num=power(x, y/2); 

导致堆栈溢出。在 Visual C++ 中，它也给了我一个明确的警告:“C4717:'power':所有控制路径的递归”

递归总是且绝对需要一个结束条件，即停止。

你在 power() 中做的第一件事就是一次又一次地调用 power() ，......，再一次:

double power(double x, int y) { 
    double num=power(x, y/2);    // <- call myself again forever
    // other code
 }

由于没有链接到该调用的停止条件，您将永远调用 power() - 或者直到始终有限的调用堆栈最终耗尽。

请记住，至少每次调用 power() 的返回地址都存储在堆栈中。将您的实现与正确的算法进行比较。你会发现第一个调用不是在那里进行的，而是更像是这样的:

double power(double x, int y)
{

   if(x==0) {   
        return 0;  // stops recursion
   }

    if(y==0) {   
        return 1;    // stops recursion 
    }

    if( (y % 2) == 0) {
        num=num*num;
        y=y/2;
        return num;     // stops recursion
    }

    num=x*power(x, y-1);   // another recursive call
    y=y-1;
    return num;
 }