`
imdxt1986
  • 浏览: 16201 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

递归 n的阶乘

 
阅读更多

1. 递归算法解题步骤

(1) 分析问题、寻找递归关系。找出大规模问题和小规模问题的关系。
(2) 找出停止条件,控制递归。
(3) 设计函数、确定参数。

  1. *阶乘的例子。其实递归递归,从字面上解释就是在方法本身调用自己的方法,或者间接调用;看上面的程序,拿multiply(5)来说:
  2. *n=5;执行5*multiply(4);
  3. *--------------------
  4. *这时候看multiply(4)
  5. n=4执行4*multiply(3);
  6. -------------------
  7. 看multiply(3)
  8. n=3,执行3*multiply(2);
  9. ---------------
  10. mulitply(2);
  11. n=2执行2*mulitply(1);
  12. 这时候,return1;往上返回
  13. 2*1向上返回
  14. 3*(2*1)向上返回
  15. 4*(3*(2*1))向上返回
  16. 5*(4*(3*(2*1)))=120
  17. 所以程序输出120;S
  18. 这事简单的递归的例子;所以可以看出来递归的关键得有递归出口(本体的If语句),还有递归方法
  19. *@paramn
  20. *@return
  21. */
  22. publicstaticintmultiply(intn){
  23. if(n==0){
  24. return1;
  25. }else{
  26. returnn*(multiply(n-1));
  27. }
  28. }
  29. /**
  30. *计算二进制中1的个数,
  31. *N为奇数,其1的个数等于N/2二进制中表示1的个数加1
  32. *例子:
  33. *num=13
  34. *1.getBinary(13/2=6)+1;调用getBinary(6/2=3)+1返回2+1=3
  35. *2.getBinary(6/2=3);进入方法,调用getBinary(1)+1=2;
  36. *3.getBinary(1)+1;getBinary(1)返回1,getBinary(1)+1实际返回2
  37. *从步骤3返回1+1;
  38. *再返回到步骤2,没有做运算
  39. *再返回到步骤1
  40. *@paramnum
  41. *@return
  42. */
  43. publicstaticintgetBinary(intnum){
  44. if(num==1)
  45. return1;
  46. if(0==num%2){//是否为偶数
  47. returngetBinary(num/2);
  48. }else{
  49. returngetBinary(num/2)+1;
  50. }
  51. }
  52. /**
  53. *利用位移来解决n>>1右移一位,相当与n/2
  54. *@paramn
  55. *@return
  56. */
  57. publicstaticintgetBinary2(intn){
  58. if(n==0){
  59. returnn;
  60. }
  61. //为偶数
  62. if(n%2==0){
  63. returngetBinary2(n>>1);
  64. }else{
  65. //若N是奇数...等于N/2的二进制中1的个数加1
  66. returngetBinary2(n>>1)+1;
  67. }
  68. }
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics