通过递归的方法输出组合数（C语言实现）

具体题目如下：

利用递归方法找出自然数1，2，3.....，n中任取r个数的所有组合

首先确认递归算法是一个自身函数调用自身函数的一种方法，因此要从n中取任意个数可以从n开始选择，对于每一个数都有两种选择，选择其是组合中的数，或者不是组合中的数。因此可以将递归函数设置为combine(int n，....),这一次函数运行则有两种选择，将n加入组合中，或者不将n加入组合。

可以确认：

conbine(int n, ....){

        conbine(n-1, ...);//不将n加入组合，并直接进入下一次递归

        conbine(n-1, ...);//将n加入组合中，再进入下一次递归

}

除了确定递归函数的递归主体外，还要确认递归函数的出口，很容易想到，出口应该是当组合中包含了r个数字时。

因此可以确认：

conbine(int n , int r .....){

        if(组合中数字个数等于r){

        输出组合中所有数字；

        return；//停止这一组，使得函数递归回

        }

}

而组合中的数字呢，由于我们是从最大的数开始进行压入的，所以可以利用栈的先进后出的特性使得大的数反而后输出，从而使结果输出是由小到大排序。因此可以选择用栈进行保存组合。

将代码贴出：

#include
struct Stack{
	int st[10];
	int top=-1;
};//定义+初始化栈 
void push(struct Stack &st,int e){
	st.top++;
	st.st[st.top]=e;
	return;
}//压入元素 
void pop(struct Stack &st,int &e){
	if(st.top!=-1){
		e=st.st[st.top];
		st.st[st.top]=NULL;
		st.top--;	
	}
}//删除栈中元素 
void printfstack(struct Stack st){
	int x;
	while(st.top!=-1){
		pop(st,x);
		printf(" %d ",x);
	}
	puts("") ;
	return;
}//输出栈中元素 
void combine(int n,int r,struct Stack st){  //传入的栈不会因为后续函数的变化而受到影响 
	if(st.top==r-1){		//当栈中有r个元素时输出栈中所有元素 
		printfstack(st);
		return;
	}
	else{
		if(n>0){		//当栈中元素小于r个时，并且n大于0，则分两种情况 
			combine(n-1,r,st);   //不压入当前n，直接进行下一次combine（n-1） 
			push(st,n);			//压入当前元素n，进行combine（n-1） 
			combine(n-1,r,st);
		}else{
			return;
		}
	}
	return;
}
int main(){
	struct Stack st,st1;
	combine(10,4,st);
	return 0;
}