浅谈C语言使用递归计算整数的整数次幂运算（平方、立方等）——递归的简单应用

古城微笑少年丶 2023-07-03 12:22 43阅读 0赞

# 浅谈C语言使用递归计算简单的整数的整数次幂运算 #

**1、什么是递归？**  
笼统地说，递归指的是一种在计算中每一步都要调用到前一步或者前几步结果的计算过程，其中包括了**递归部分**和**返回部分**。递归部分便是递归函数主要的执行部分，而返回部分则负责告诉函数什么时候停下来，显然没有返回部分的递归函数没有什么意义。

笔者总结递归过程是，逐渐拆分，向下传递，向上回归的过程。阶乘和幂运算就是其中的简单应用，以阶乘为例，5的阶乘在用以递归的视角来看便先把5的阶乘拆分成5！=5 \* 4！=5 \* 4 \* 3 ！=5 \* 4 \* 3 \* 2！=5 \* 4 \* 3 \* 2 \* 1，以此向下传递计算各数（4！，3！，2!）的阶乘的任务，依次解决后再向上传递每一步的答案，而不是直接得出 5！=5 \* 4 \* 3 \* 2 \* 1。这样看来递归就是把复杂问题拆分成多个简单问题依次解决得到复杂问题的答案的方法。

从阶乘我们可以总结出，递归是用来解决“套娃问题”（禁止套娃），由多个结构类似的简单问题组成的复杂问题就可以通过递归解决。

当然，笔者的理解还很浅显，毕竟只是初学，也不能把递归这个过程讲的很清楚，但是我发现在编写自己或者理解他人的递归程序时在纸上把过程一步步写出来可以起到很大的帮助，光在脑子里想反倒会浪费很多时间。理论讲的差不多了，可以开始打码了。

**2、代码实现**  
基于不同的计算方法，解决整数的整数次幂运算有两种方法。  
方法一 直接计算，正常人直接能想到的，即 xn=x \* x \* x \*…，代码实现也很简单，如下

int power(int num,int index) //num表示底数，index表示指数
    { 
        if(index==0)    
        { 
            return 1;
        }		                //返回部分
        else 
        	return num*power(num,index-1); //递归部分
    }

方法二 拆分计算，这种方法是笔者一开始在网上搜索资料时候看到的，个人认为这种方法不是很有必要因为在达到相同效果的情况下这种方法可读性稍差，但是既然看到了就拿出来看看，代码如下

int powerII(int num,int index)
    { 
        if(index == 0)
        { 
            return 1;
        }//返回部分
        else if(index%2==1)
            return num*power(num,index-1);
        else   //index%2==0
        { 
            int z=power(num,index/2);
            return z*z;
        }//递归部分
    }

实话说一开始我没有搞懂它是怎么算的，在纸上比划了一会才看明白，它分了几种情况，  
其主要原理如图，![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTc2NjE5OQ_size_16_color_FFFFFF_t_70]  
具体计算过程如下图，  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTc2NjE5OQ_size_16_color_FFFFFF_t_70 1]  
当指数为0的时候直接通过通道3完成计算，当指数为偶数时，通过通道2进行运算同时在每次计算时指数除以2直到为0，当指数为基数时，先通过通道1，对应图1中间x·这一步，然后就是重复当指数为偶数的部分即可。(虽说这种方法确实有点烦，但是帮我复习了if else结构还加深了对于返回值的理解。)

完整代码如下

#include <stdio.h>
    
    int power(int num,int index);//num表示底数，index表示指数
    int powerII(int num,int index);
    
    int main()
    { 
    
        int x,y;
    
        printf("想算哪个整数的几次方？\n");
        printf("输入你想算的数字吧，整数在前，指数在后，中间用半角逗号分隔：");
        scanf("%d,%d",&x,&y);
        printf("%d的%d次方是%d\n",x,y,power(x,y));
        printf("%d的%d次方是%d\n",x,y,powerII(x,y));
    
        return 0;
    
    }
    
    
    int power(int num,int index)
    { 
        if(index==0)
        { 
            return 1;
        }
        else return num*power(num,index-1);
    }
    
    int powerII(int num,int index)
    { 
        if(index == 0)
        { 
            return 1;
        }
        else if(index%2==1)
            return num*power(num,index-1);
        else
        { 
            int z=power(num,index/2);
            return z*z;
        }
    }

**3、总结一下**  
用递归解决这个问题的**关键**就是在于理解**逐渐拆分，向下传递，向上回归**这个过程，一旦理解核心部分，剩下的就是代码实现部分了。  
推荐各位去看这位大佬的文章，递归讲的很清楚，本文递归部分和返回部分的命名借鉴于此文

> https://blog.csdn.net/weixin\_43405546/article/details/83045725

第二种算法的代码最初来自这篇百度知道

> https://zhidao.baidu.com/question/553192369.html

解决这个问题还有很多其他的方法，用循环也可以解决，还有叫快速幂的方法（还没搞懂怎么回事。。），各位可以自己探索看看。我本身也是初学，有什么错误欢迎指正。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTc2NjE5OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200207122622129.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTc2NjE5OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTc2NjE5OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200207124445339.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTc2NjE5OQ==,size_16,color_FFFFFF,t_70