C语言猴子吃桃问题递归法

Question

我写的是这样的：
#include <stdio.h>
void main()
{
long tao(int r_day);
long x;
int day,reverse_day;
day=1;
reverse_day=11-day;
x=tao(reverse_day);
printf("total=%d\n",x);
}
long tao(int r_day)
{
long y;
if(r_day==1)
y=1;
else
y=2*(tao(r_day-1)+1);
return y;
}
----------------------------
我的问题：
y=2*(tao(r_day-1)+1);

这一句怎样能写成 /2-1的形式？（第2天又将吃剩的桃子吃掉一半，又多吃了一个）

我在百度上看到一个解法是这样的：
#include <stdio.h>
const unsigned int &fun_last(const int &n,const int &day)
{
if(n<0) return -1;
if(day==1) return n;
return fun_last(2*(n+1),day-1); //当天剩n个，前一天剩下2*(n+1)个
}
int main(void)
{
int day=10,n=1;
printf("第一天摘下%d个桃子\n",fun_last(n,day));
return 0;
}
我对递归的概念不是很清晰，
他的这个解法是不是函数在递归到第10次调用的时候就直接返回一个值了？
而我的解法是不是第10次调用以后需要逐级回退（弹出栈）最后才得到最终的值？
而且他的参数和返回值都是引用，是不是都是从栈里直接取值，而不用拷贝各个形参和返回值变量？
感觉学谭教授的书很难写出他这样的代码。

Answer 1

/*猴子第一天摘下N个桃子，当时就吃了一半，还不过瘾，就又多吃了一个。*/
/*第二天又将剩下的桃子吃掉一半，又多吃了一个。*/
/*以后每天都吃前一天剩下的一半零一个。*/
/*到第10天在想吃的时候就剩一个桃子了*/
/*问第一天共摘下来多少个桃子？*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

/*第n天所剩桃子数*/
int getPeachNumber (int n) {
int num; /*定义所剩桃子数*/
int i=0;
if (n==10)  
       return 1; /*递归结束*/
else {
num = getPeachNumber(n+1)*2 + 2; /*递归*/
printf("第%d天：%d个桃子\n", n, num); /*第n天剩num个桃子*/ 
}
    return num;
}

int main (void) {
    int num;
    
    puts ("每天剩余的桃子数：");
    num = getPeachNumber (1);
    putchar ('\n');
    
    puts ("================================================================");
    putchar ('\n');
    printf("猴子第一天摘了%d个桃子！\n", num);
putchar ('\n');

getch (); /*屏幕暂留*/
return 0;
}

运行结果

Answer 2

是这样的吧！两个参数，一个是最后桃数，一个是日期序数！
这和谭教授的书有啥关系？？？
任何课本都只能教你一些基本的东西，其他的要自己积累！！！
const unsigned int & 返回没有必要！！

const int fun_last(const int &n,const int &day)

{
if(n<0) return -1;
if(day==1) return n;
return fun_last(2*(n+1),day-1); //当天剩n个，前一天剩下2*(n+1)个
}
写成这样更好，因为C，C++通用，内部类型，不需要使用引用参数！
const int fun_last(const int n,const int day)
{
if(n<0) return -1;
if(day==1) return n;
return fun_last(2*(n+1),day-1); //当天剩n个，前一天剩下2*(n+1)个
}
if(n<0) return -1; 保证不出错
if(n<0) return 0;？？？？？ 保证不出错
if(day==1) return n;最后一天，只剩这么多了
return fun_last(2*(n+1),day-1);上一天 比今天还多一个再翻倍

从思路来说他的这个更好，但也不是谭教授的书让你的代码难看吧！！
从代码上看实际上是一样的；
只是通常不这样写
if(r_day==1)
y=1;
else
y=2*(tao(r_day-1)+1);
直接写
if(r_day==1)return 1；
return 2*(tao(r_day-1)+1);
因为这样的代码更干净，更清晰！！！
而且这种写法和递归没什么关系！！
这只是让代码好读一点，找错更简单一点！！

如果代码里有些条件语句
主要逻辑代码很长，另外一些逻辑代码很简短，这些简短代码就可以直接返回；
从而使程序的主要逻辑清晰，突出！！

就是说
像这样的代码
if(r_day==1)
y=1;
else {
。。。。。。。。。。
y=2*(tao(r_day-1)+1);
}
直接写成这样的代码更好
if(r_day==1)return 1；
。。。。。。
return 2*(tao(r_day-1)+1);
这不是教科书的问题！！！
至于递归你的代码和他的没有什么区别！
他的可以是任何桃数算起，你的只能从1算起，区别在这里

day=1;
reverse_day=11-day;
x=tao(reverse_day);
你的代码也可以写成x=tao(10);呀
是你非要说现在是最后一天，
非要写成这样的
day=1;
reverse_day=11-day;

递归调用，出栈入栈实际上是函数调用本身实现的；
任何一个实现了函数调用的语言，都可以实现递归调用！！！
递归函数和非递归函数的唯一区别，是有没有自己调用自己！不管是直接还是间接的。

只要局部变量放到栈上，编译器不用额外做任何事情，都可以实现递归！！
所以递归的问题，是栈够不够用的问题。
递归函数并不比非递归难以实现；

由于递归调用，函数的局部参数占用空间的大小就难以估计了
而非递归函数很好估计！！！这才是有些系统不支持递归，
以及有些系统对递归专门处理（比如Keil C）的原因

问题：我对递归的概念不是很清晰，
他的这个解法是不是函数在递归到第10次调用的时候就直接返回一个值了？
而我的解法是不是第10次调用以后需要逐级回退（弹出栈）最后才得到最终的值？
而且他的参数和返回值都是引用，是不是都是从栈里直接取值，而不用拷贝各个形参和 返回值变量？

解答：1）两个解法效果一样
2）引用没有起到任何作用！！！因为int是内部类型，不是巨大对象类型
PS：关于递归
1）基本情况，总有一些情况不通过递归调用，可以直接得出结论！
2）层层推进，每次向解决问题靠近一步！
3）合成效益原则，递归要高效实现，计算斐波那契数列那样的函数不要用递归
这个是从一本书上看到的大意如此，可能有些遗漏
这是使用递归的一些原则！
其他方面，多看些数据结构方面的书吧！！本回答被网友采纳

Answer 3

所以，现在！两个参数，最后的桃数字，日期序列号！
这种关系，谭教授的书籍，还等什么？ ？ ？
教科书可以教你一些基本的东西，他们积累的！ ！ ！
const的无符号整数与回报是没有必要的！ ！

const int的fun_last（const int的N，const int的和天数）

{
（N <0）返回-1;
（天== 1）返回n
的回报fun_last（2 *（N +1），每天1）左边n / /日，前休息之天2 *（N +1）个
}
写这样更好，因为C，C + +通用的，内部的类型，也不需要使用引用参数！
const int的fun_last（const int的N，const int的一天）
{
（N <0）返回-1;
（天== 1）返回n; />的回报fun_last（2 *（N +1），天-1）; / /天左边n的前一天，其余的2 *（N +1）
}
（N <0）返回-1，确保没有错误
（N <0）返回0; ？ ？ ？ ？确保没有错误
（天== 1）返回n的最后一天，只有这么多
回报fun_last（2 *（N +1），天-1）;比今天多了一个，然后一倍

他更好的想法，而不是陈教授的这本书使你的代码丑陋！ ！
从代码的角度来看，实际上是相同的;
只是通常不写
（r_day == 1）
Y = 1;
其他 /> Y = 2 *（陶（r_day-1）+1）;
直接写

（r_day == 1）返回1;
RETURN 2 *（TAO （r_day-1）+1）;
因为这段代码是更清洁，更清晰！ ！ ！
措辞和递归没有！ ！
这仅仅是一个良好的阅读，使代码是放错地方的更容易一些！ ！

一些条件语句中的代码
主要逻辑代码，一些逻辑代码是非常短暂的，这些短代码，可以直接返回;
如此明确的程序逻辑，突出！ ！

这样的代码
（r_day == 1）
Y = 1;
其他{
。 。 。 。 。 。 。 。 。 。
Y = 2 *（陶（r_day-1）+1）;
}
直接这样写代码，更好地
（r_day == 1）返回1;
>。 。 。 。 。 。
回报率2 *（陶（r_day-1）+1）;
这是不是一本教科书！ ！ ！
至于递归您的代码并没有什么区别！
可以是任何桃数计数，你只能从1数，这里的区别

天= 1;
reverse_day = 11天;
X =涛（reverse_day）;
你的代码也可以写为x =涛（10）;
你说，现在是最后一天，
写的那么
天= 1;
reverse_day = 11天;

递归调用，协议栈，堆栈实际上是一个函数调用来实现;
实现语言的函数调用递归调用！ ！ ！唯一的区别，是的
递归函数和非递归函数调用自身的！无论是直接或间接的影响。

只要为局部变量在堆栈中，编译器没有做任何额外的费用，递归可以实现了！ ！
递归栈不够的。
递归函数并不难实现比非递归的;

大小的空间是难以估量的递归调用的函数的局部参数<BR /而不是递归函数估计！ ！这是一些系统不支持递归，
系统，一些的递归专门的处理（如Keil C语言）的原因。

问题：我的递归的概念不是很清楚
直接返回一个值时，该解决方案是不是一个函数的递归调用的10倍？
我的解决方案是不是呼叫后第十步一步回滚（弹出）终于得到了最终的价值吗？
和他的参数和返回值是参考值是直接从栈中，而无需将每个参数和返回值的变量？
答案：1）两个解决方案的效果
2）没有起到任何作用！ ！ ！诠释内部的类型，而不是一个巨大的物体类型
PS：递归
1）基本情况，总有一些情况下，通过递归调用，可以直接结束！
2）层层推进更近了一步，每次解决问题！
3）合成的效益，有效地执行递归，计算斐波那契数列的函数，不要使用递归
这是从一本书上看到的效果，可能会有一些失踪
这是一些使用递归的原则！
其他方面的一些数据结构的书友会！ ！

Answer 4

一个猴子摘了一些桃子,它每天吃了其中的一半然后再多吃了一个,
直到第10天,它发现只有1个桃子了,问它第一天摘了多少个桃子?
猴子分N天吃完了桃子,要想求出第1天的桃子数,就先要求出第2天的桃子数,.......因此,有:
a1=(a2+1)*2;
a2=(a3+1)*2;
a3=(a4+1)*2;
......
a9=(a10+1)*2;
a10=1;
现在就知道了算法,我们可以用递归来求解:
int qiu(int a,int n)
{
if(n==1) a=1; //第10天就只剩1个了
else a=(a(n-1)+1)*2; //前一天总比后1天多一半加1
}
-------------------------------------
#include<stdio.h>
int qiu(int a,int n);
main(){
int zuih=1,tians=10;//最后一天的个数,天数
long sum;
sum=qiu(1,10);
printf("di yi tian you %ld ge.\n"):
}
int qiu(int a,int n)
{
if(n==1) a=1; //第10天就只剩1个了
else a=(a(n-1)+1)*2; //前一天总比后1天多一半加1
}

Answer 5

Private Sub Command1_Click()
Dim a, b, s As Integer
a = 1'第9天吃完后就是这一个了，令a=1
For i = 9 To 1 Step -1 '吃之前的桃子数 ，从第九天吃之前开始算起
a = (a + 1) * 2 '每天吃之前剩的桃子数
Next
Print a
End Sub
结果1534个，不是知道是什么猴子这么能吃。。。。