递归函数例子(递归函数的例子)

张工 2022-06-21 20:16:57 阅读:16
  

  第一天,猴子摘了很多桃子,马上吃了一半,但是不够,所以他又吃了一个。第二天早上,我把剩下的桃子吃了一半,又吃了一个。每天早上吃前一天剩下的一半一个。到了第10天早上,再想吃的时候,看到只剩一个桃子了。第一天你选了几个?

  向后考虑,有迭代表达式:

  桃子=(桃子1)* 2;//前一天的桃子数和当天的桃子数之间的关系

  //2减1除1加1乘2是正向思维和反向思维的关系,也就是一种表达方式的转换。

  //int count=peach count(10);

  int peachCount(int days)

  {

  int peaches=1;//最后一天的桃子数

  同时(第1天)

  {

  桃子=(桃子1)* 2;

  天-;

  }

  还桃;

  }考虑递归。有递归表达式:

  peachcount(n)

  Peachcount(1)=1 //最后一天(最后一天)

  (peachCount( - n) 1)*2 //n1

  代码:

  //peachcountrycursive(10);//1534

  int peachCountRecursive(int day)

  {

  If(day==1) //最后一天

  返回1;

  其他

  return(peachcountrycursive(-day)1)* 2;

  }对于递归,三个概念很重要:

  子问题1的解与规模为N的整个问题的解具有相同的表达式(子问题与原问题具有垂直齐次关系)。当规模为n(1)时,有一个直接解,这就是递归结束条件,也称为递归出口。

  2递归函数的两个阶段(基于递归函数中自己调用的语句):递归前进阶段和递归返回阶段。推进段形成函数n次(调用参考点),返回段形成函数n次(参考点ret,如果是尾递归,直接返回)。算法的递归思想分为向前和向后两种,这与递归思想的两个阶段形成对比。

  递归函数的递归扩展和收缩是由编译器隐式维护的堆栈数据结构实现的。在递归扩展阶段,N次调用形成N个堆栈帧,在回滚收缩阶段,N个堆栈帧被逐一返回(通过移动EBP和ESP寄存器指针)。栈上的数据一方面是函数回滚到调用点的需要(记录回滚地址),另一方面是回滚阶段需要用到的递归函数参数和局部变量的历史值。如果用循环重写非尾部递归,需要手动维护一个堆栈数据结构来记录历史值。

  -结束-

二维码