在'while循环'中实现印度算法.我做错了什么？

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;
 }