本文主要是介绍方法递归-结合案例阶乘问题、求和问题和猴子吃桃问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
方法递归
递归是一种算法 在程序设计语言中广泛应用.
从形式上来说:方法调用自身的形式称为方法递归(recursion).
递归的形式:
- 直接递归:方法调用自己。
- 间接递归:方法调用其他方法,其他方法又回调方法自己。
//直接方法递归
public static void test1(){System.out.println("----test1----");test1();
}
//间接方法递归
public static void test2(){System.out.println("----test2----");test3();
}
public static void test3(){test2();
}
使用方法递归时需要注意的问题:
递归如果没有控制好终止,会出现递归死循环,导致栈内存溢出错误。
递归案例(一)-计算机n的阶乘
需求:计算n的阶乘,5的阶乘=1x2x3x4x5;6的阶乘=1x2x3x4x5x6;
分析:
①假如:我们存在一个公式是f(n)=1x2x3x4x5x6x7…(n-1)*n;
②那么公式等价于f(n)=f(n-1)*n;
③如果求的是1-5的阶乘的结果,我们手工应该如何应用上述公式进行计算
f(5)=f(4)x5;
f(4)=f(3)x4;
f(3)=f(2)x3;
f(2)=f(1)x2
f(1)=1;
public static int f(int n){if(n==1){return 1;}else{return n*f(n-1);}
}
递归算法三要素:
- 递归的公式;
- 递归的终结点;
- 递归的方向必须走向总结点。
递归案例(二)-求1-n的和
需求:计算n的阶乘,1-5的和=1+2+3+4+5;1-6的和=1+2+3+4+5+6;
分析:
①假如:我们存在一个公式是f(n)=1+2+3+4+5+6+7…(n-1)+n;
②那么公式等价于f(n)=f(n-1)+n;
③如果求的是1-5的和的结果,我们手工应该如何应用上述公式进行计算
f(5)=f(4)+5;
f(4)=f(3)+4;
f(3)=f(2)+3;
f(2)=f(1)+2
f(1)=1;
public static int f(int n){if (n==1){return 1;}return n+f(n-1);
}
递归案例(三)-猴子吃桃问题
问题描述:猴子第一天摘下若干桃子,当即吃了一半,觉得好不过瘾,于是又多吃了一个,第二天又吃了前天剩余桃子数量的一半,觉得好不过瘾,于是又多吃了一个以后每天都是吃前天剩余桃子数量的一半,觉得好不过瘾,又多吃了一个等到第10天的时候发现桃子只有1个了。
需求:请问猴子第一天摘了多少个桃子?
分析:
①f(10)=1
②公式f(x)-f(x)/2-1=f(x+1)
③变形:f(x)/2-1=f(x+1)
④变形2:f(x)=2*f(x+1)+2
public static int f(int n){if(n==10){return 1;}else{return 2*f(n+1)+2;}
}
这篇关于方法递归-结合案例阶乘问题、求和问题和猴子吃桃问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!