C语言经典递归算法之和式分解

朴灿烈づ我的快乐病毒、 2023-01-10 14:35 124阅读 0赞

### 文章目录 ###

*   *  一、递归算法
     *  二、和式分解

## 一、递归算法 ##

**1、递归**  
递归就是自己调用自己，它是设计和描述算法的一种有力工具，常常用来解决比较复杂的问题。  
递归是一种分而治之，将复杂问题转化难为简单的问题的求解方法。

**2、递归的优点**  
使用递归编写的程序简洁、结构清晰，程序的正确性很容易被证明，不需要了解递归调用的具体细节。

**3、递归的缺点**  
递归函数在调用过程中，每一层调用都需要保存临时变量和返回地址、传递参数，因此递归函数的执行效率低。

## 二、和式分解 ##

**1、原理分析**  
（1）引入数组a，用来存放分解出来的和数，其中，a\[k\]存 放第k步分解出来的和数。

（2）递归函数应设置三个参数：第1个参数是数组名a,用来将数组中的元素传递给被调用函数；  
第2个参数i表示本次递归调用要分解的数；  
第3个参数k是本次递归调用将要分解出的第k个和数。

**2、C语言实现和式分解**

#include <stdio.h>
    #define N 50
    void rd(int a[], int i, int k);
    void main()
    { 
    	int n, a[N];
    	printf("请输入一个正整数：n(0<=n<50)：");
    	scanf("%d",&n);
    	a[0]= n;
    	printf("和式分解结果：\n");
    	rd(a,n,1);
    }
    void rd(int a[], int i, int k)
    { 
    	int j, p;
    	for(j=i; j>=1; j--)
    	{ 
    		if(j<=a[k-1])
    		{ 
    			a[k]=j;
    			if(j==i)
    			{ 
    				printf("%d=%d",a[0],a[1]);
    				for(p=2; p<=k; p++)
    					printf("+%d", a[p]);
    				printf("\n");
    			}
    			else
    				rd(a, i-j, k+1);
    		}
    	}
    }

![01][]

![02][]

参考文献：《The Function and Algorithm of Program Language C/C++》

[01]: /images/20221119/afb44014cb8c40f48226096ddf6b3281.png
[02]: /images/20221119/26541bed8f0b4c61a86361db7fca9ddd.png