递归函数的几个例子

　

递归函数

/*1.一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。

这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过

每个村子卖出多少只鸭子?*/

#include<stdio.h>
int q(int duck,int village)//定义递归函数，参数为鸭子数和村子数
{
	if(village==0)		//未经过村子时的鸭子为总数
		printf("总共有%d个鸭子。\n",duck);
	else				
	{
		duck=(duck+1)*2;	
		printf("在第%d个村子卖出%d个鸭子,剩余%d个鸭子。\n",village,duck/2+1,duck/2-1);
		return q(duck,village-1);
	}
}

//主函数
void main()
{
	int d=2;//鸭子数
	int v=7;//村庄
	q(d,v);
	getchar();
}

//方法二,更简单方便
/*
#include <stdio.h>
int f(int n)
{
int num;
if(n==8)//第7个村子过后，也就是到第八个村子时还有2只鸭
{
return 2;
}
else
{
num =(f(n+1)+1)*2; //递归调用
printf("第%d个村子卖鸭子%d只\n",n,num/2+1);
}
return num;
}
int main()
{
int num = f(1);
printf("总共赶鸭子%d个\n",num);
return 0;
}
*/

/*2.角谷定理。输入一个自然数，若为偶数，则把它除以2，

若为奇数，则把它乘以3加1。经过如此有限次运算后，总可

以得到自然数值1。求经过多少次可得到自然数1。*/

#include<stdio.h>
//定义递归函数，参数为数字和步骤数
int jg(int n,int step)
{
	if(n!=1)
	{	
		if(n%2 == 0)
		{
			printf("%d ", n);
			n = n / 2;	
		}
		else if (n % 2 == 1)
		{
			printf("%d ", n);
			n = 3 * n + 1;
		}
		return jg(n, step + 1);
	}
	else
	{
		printf("%d ", n);
		step++;
	}
	printf("\nSTEP=%d\n",step);//输出步骤数
}

//主函数
int main()
{
	int s=0;
	int num;
	printf("请输入一个数：");
	scanf("%d",&num);//输入数字
	jg(num,s);
	return 0;
}

//方法二，更简单
/*#include <stdio.h>
int f(int i)
{
	printf("%d ", i);
	if (i == 1)return 1;
	if (i %2==1)
		return f(i * 3 + 1) + 1;
	else
		return f(i / 2) + 1;
}
int main()
{
	int i, w;
	printf("请输入数字：");
	scanf("%d", &i);
	w = f(i);
	printf("\nSTEP=%d\n", w);
}
*/

/*3.电话号码对应的字符组合：在电话或者手机上，一个数字如2对应

着字母ABC，7对应着PQRS。那么数字串27所对应的字符的可能组合

就有3*4=12种（如AP，BR等）。现在输入一个3到11位长的电话号码，

请打印出这个电话号码所对应的字符的所有可能组合和组合数。*/

#include <iOStream>
using namespace std;
#pragma warning(disable:4996)// 将4966警报置为失效
const char word[10][5] = { "  ", " ", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" };
const int num[10] = { 0, 0, 3, 3, 3, 3, 3, 4, 3, 4 };
int input[11]; // input[i]表示：和第i个数字对应应该输出字符串的第几个字母
int turn[11]; // 把number转化成数字后存在里面

//递归函数,参数为输入数字
int func(int number)
{
	int m = 0;//定义起始转化数字为0
	if (number < 0)
	{
		return 0;
	}
	while (number)// 把数字拆开并记录
	{
		turn[m] = number % 10;		
		if (turn[m] == 1 || turn[m] == 0)// 转化0或者1，就直接返回
			return 0;
		number /= 10;  // number=number/10;
		++m;
	}
	int len = m; // 记录数字有多少长度
	int word_sum = 0; // 用来表示输出字母组合的当前个数
	memset(input, 0, sizeof(input)); // 初始化时都为0
	while (true)
	{
		// 根据input数组中的计算所得的每个数字对应的字符串应该输出的字母的索引输出当前字符组合。
		cout << "生成组合为：";
		for (int i = len - 1; i >= 0; i--)
		{
			cout << word[turn[i]][input[i]];
		}
		cout << endl;
		++word_sum;
		int k = len - 1;// 数组下标从0开始
		while (k >= 0)//用循环不断向前进位
		{
			if (input[k] < num[turn[k]] - 1)
			{
				++input[k];
				break;
			}
			else
			{
				input[k] = 0;
				--k;
			}
		}
		if (k < 0)// input的各个元素都变为零
		{
			break;
		}
	}
	return word_sum;
}

//主函数
int main()
{
	int number;
	printf("请输入数字：\n");
	while (scanf("%d", &number))
	{
		printf("组合总数为：%d \n", func(number));
	}
	return 0;
}

/*日本著名数学游戏专家中村义作教授提出这样一个问题：

父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将

分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7

给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到

后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子

分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。

结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少

桔子？*/

#include<stdio.h>
#define MAX 8//定义分母最大值
#define MIN 3//定义分母最小值
int ora[5][2] = { {0,0},{ 0,0 },{ 0,0 },{ 0,0 },{ 0,0 } };

/*定义递归函数，参数为孩子数组，
c[i][0]表示第i个孩子分出去桔子的总数
c[i][1]表示第i个孩子从国王出得到桔子的总数*/
int orange(int c[5][2], int i)
{
	int average = 2520 / 6;
	if (i == 0)
	{
		c[i][1] = (average - average / (MIN - 1))*(MAX - i) / (MAX - 1 - i);//第一个孩子从国王那里得到桔子数为
		//平均数减去最后一个孩子分出去的部分后乘以8/7
		c[i][0] = c[i][1] - (average - average / (MIN - 1));//第一个孩子分给第二个孩子的桔子数量
	}
	else
	{
		c[i][1] = average*(MAX - i) / (MAX - 1 - i) - orange(c, i - 1);//第i个孩子从国王那里得到桔子总数
		c[i][0] = c[i][1] + orange(c, i - 1) - average;//第i个孩子分给下一个孩子的橘子数量
	}
	int p = c[i][0];
	return p;
}

//主函数
void main()
{
	orange(ora, 5);
	for (int j = 0; j <= 5; j++)
	{
		printf("第%d个孩子向下一个孩子分出%d个桔子。\n", j + 1,ora[j][0]);
	}
	printf("国王最初分配桔子情况如下：\n");
	for (int k = 0; k <= 5; k++)
	{
		printf("原来第%d个孩子从国王那里得到%d个桔子。\n", k + 1, ora[k][1]);
	}	
	getchar();
}

相关阅读

年终盘点：2018年，这些精彩的刷屏案例你看过几个？

距离2018年结束只剩下7天了，一到年终岁末，回顾、盘点就成为最常出现的词语。本文也不例外，纵观这一年，你会发现今年的营销圈格外热闹，

淘宝刷单维度是什么意思？刷单有几个维度？

随着淘宝规则逐年加强，淘宝稽查系统查的越发严格，相当多的小伙伴刷单都被抓怕了，明晰、扣分、降权，天然查找流量下降，店铺的归纳质量得

小学生怎么网赚？几个好点子帮您网赚“锦上添花”

  小学生怎么网赚？这是一个网赚圈内的比较热烈的话题。究竟小学生适合不适合做网赚？也是争论不休，有的说可以有的说不行。由于小学

淘宝刷手需要几个号?小号申请后怎么养?

现在的互联网，已经给了想通过网络赚钱的兼职很多机会。比如很火的多多进宝、淘宝客、阿里众包等等。但小编觉得目前最火、做的人最

几个淘宝店铺左侧栏190宽黑色闪图客服中心图片素材

素材类型：190宽淘宝客服中心图片; 实用模块：淘宝店铺左侧栏自定义模块; 素材风格：金色高档; 适用店铺：通用淘宝店铺； 图片大小：多