黑马程序员技术交流社区

标题: 递归的问题 [打印本页]
作者: 悠然丶    时间: 2014-4-16 22:08
标题: 递归的问题
本帖最后由 悠然丶 于 2014-4-16 23:31 编辑

     我对递归的问题不是很了解,只是知道递归就是方法自己调用自己,就是一个循 环
   说明递归的退出条件,怎么就退出循环了~~~
计算 1*1 + 2*2 + 3*3 + … + n*n 的和  这个用递归怎么解决?
public static int count(int n) {        // 计算 1*1 + 2*2 + 3*3 + … + n*n 的和
                int result = 0;
                for (int i = 1; i <= n; i++)        // 定义循环, 从1循环到n
                        result += i * i;                        // 每次i都是一个1到n之间的值, 把这些值的平方累加起来
                return result;
        }
作者: 赵小豪    时间: 2014-4-16 22:18
分享：http://blog.csdn.net/shixing_11/article/details/5652986
  1. package apistudy;  
  2. import java.math.BigDecimal;  
  3. public class JieCheng  
  4. {  
  5.     public static void main(String[] args)  
  6.     {  
  7.         int num = Integer.parseInt(args[0]);  
  8.         System.out.println("递归算法"+num+"的阶乘= "+CalcJieCheng(num));  
  9.         System.out.println("非递归算法"+num+"的阶乘= "+CalcJieCheng2(num));  
  10.         System.out.println("1*1! + 2*2! + 3*3! +...+ N*N! ="+CalcSUM(num));  
  11.     }  
  12.     // desc: 求N的阶乘,递归算法实现  
  13.     public static BigDecimal CalcJieCheng(int n)  
  14.     {  
  15.         BigDecimal num = new BigDecimal(n);  
  16.         BigDecimal bd = null;  
  17.         if (n == 1 || n == 0)  
  18.         {  
  19.             bd = new BigDecimal(1);  
  20.         }  
  21.         else  
  22.         {  
  23.             bd = num.multiply(CalcJieCheng(n - 1)); //multiply乘法  
  24.         }  
  25.         return bd;  
  26.     }  
  27.     //desc: 求N的阶乘,非递归算法实现  
  28.     public static BigDecimal CalcJieCheng2(int n)  
  29.     {  
  30.         BigDecimal num = new BigDecimal(1);  
  31.         for (int i = 1; i <= n; i++)  
  32.         {  
  33.             num = num.multiply(new BigDecimal(i));  
  34.         }  
  35.         return num;  
  36.     }  
  37.     //desc: 求N的阶乘并计算阶乘和  
  38.     public static BigDecimal CalcSUM(int n)  
  39.     {  
  40.         BigDecimal bigDecimal = new BigDecimal(0);  
  41.         for (int i = 1; i <= n; i++)  
  42.         {  
  43.             bigDecimal = bigDecimal.add(CalcJieCheng(i).multiply(new BigDecimal(i))); //add加法  
  44.         }  
  45.         return bigDecimal;  
  46.     }  
  47. }  
复制代码
作者: 月光海    时间: 2014-4-16 22:19
  1. public class Demo1 {

  3.         public static void main(String[] args) {
  4.                 // TODO Auto-generated method stub
  5.                
  6.                 int n=4;
  7.                 int result=count(n);
  8.                 System.out.println(result);
  9.         }
  10.         public static int count(int n) {        // 计算 1*1 + 2*2 + 3*3 + … + n*n 的和
  11.         int result = 0;
  12.         
  13.         while(n>0)
  14.         {       
  15.                 result+=n*n;
  16.                 n--;
  17.         }
  18.                              
  19.         return result;
  20. }

  22. }
复制代码
已经实现，希望能帮到你，应该是很容易理解的
作者: ^o（孤8o|狼i¤F    时间: 2014-4-16 22:36
public static void main(String[] args) {

        System.out.println(digui(1)+1);
       
        }
        public static  int digui(int num){
               
                int  sum = 0;
               
                if(num==1)
                        num = num * num;
                else
                        sum += num*num + digui(num-1);
                return sum;
               
        }

}
作者: 悠然丶    时间: 2014-4-16 22:42
月光海 发表于 2014-4-16 22:19
已经实现，希望能帮到你，应该是很容易理解的

你这个不是递归算法啊..:)
作者: 冰枫    时间: 2014-4-16 22:45
递归是函数自己调用自己，使用的时候要注意：
1.限定条件，就像是if语句中的一样，达到限定条件再往下循环就不符合条件了，就会跳出循环
2.注意递归的次数，避免内存溢出，因为递归自己调用自己，可以调用，说明原先的程序没有结束，一直调用下去，     占用的资源一直增加，可能会内存溢出。
你这里的题目：
计算 1*1 + 2*2 + 3*3 + … + n*n 的和  
首先考虑限定条件，其实1*1在最前面，在递归中计算出的第一个是跳出循环的那个表达式，也就是说1*1就是到达了限定条件，所以限定条件是x==1
表达式封装为x*x,
这样就得到了题目的编码：
public static int count(int n){
    //限定条件
    if(n==1){
        //跳出循环式表达式，也就是程序中运行到最后，但最先得出的表达式
        return 1*1;
    //实现累加
    return n*n+count(n-1);
    }
}
作者: 悠然丶    时间: 2014-4-16 22:49
^o（孤8o|狼i¤F 发表于 2014-4-16 22:36
public static void main(String[] args) {

        System.out.println(digui(1)+1);

你这个还是比较好理解的..谢谢
作者: Ricky_Nick    时间: 2014-4-16 22:53
看了楼上各位发的，也写一个仅供参考，欢迎指导
  1. public class DuiGui {
  2.                 public static void main(String[] args)
  3.                 {
  4. System.out.println("sum="+count(3));
  5.                 }
  6.                 public static int count(int n)
  7.                 {
  8.                         if(n==1)
  9.                                 return 1;
  10.                         return n*n+count(n-1);
  11.                  }
  12. }
复制代码


作者: Ricky_Nick    时间: 2014-4-16 22:54
^o（孤8o|狼i¤F 发表于 2014-4-16 22:36
public static void main(String[] args) {

        System.out.println(digui(1)+1);

你这个每一次递归，都会把sum重新初始化为0
作者: 月光海    时间: 2014-4-16 23:01
  1. public class Demo1 {

  3.         public static void main(String[] args) {
  4.                 // TODO Auto-generated method stub

  6.                 int n = 5;
  7.                 int result = 0;
  8.                 result = count(n,result);
  9.                 System.out.println(result);
  10.         }

  12.         public static int count(int n,int result) {  
  13.                
  14.                 if(n>0)
  15.                 {
  16.                         result+=n*n;
  17.                 return        count(--n,result);       
  18.                 }

  20.                 return result;
  21.         }

  23. }
复制代码
不好意思，写着写着就忘了递归的事了，修改了下代码
作者: 清风夜独醉    时间: 2014-4-16 23:07
你应该知道数学中的函数吧，其实你可以把要递归的表达式看成是一个函数f(n)，而函数f(n)和f(n-1)之间有一种关系表达式。
像你的这道题，f(n)=1*1 + 2*2 + 3*3 + … + n*n;
                     f(n-1)=1*1 + 2*2 + 3*3 + … + (n-1)*(n-1);
f(n)和f(n-1)的关系表达式就是：f(n)=f(n-1)+n*n;当n=1时，f(1) = 1；
转换成编程思想可以这么理解：
f()就是方法，n就是你要传入的参数，等号右边就是方法里的内容。当n=1时，方法返回1，作为递归的结束条件。这样一来，这个递归方法就容易写了。
  1. public class Test {
  2.         public static void main(String args[]) {
  3.                 System.out.println(count(5));

  5.         }
  6.         public static int count(int n){
  7.                 if(n == 1)
  8.                         return 1;
  9.                 return count(n-1)+n*n;
  10.         }
  11. }
复制代码



作者: 悠然丶    时间: 2014-4-16 23:08
冰枫 发表于 2014-4-16 22:45
递归是函数自己调用自己，使用的时候要注意：
1.限定条件，就像是if语句中的一样，达到限定条件再往下循环 ...

不错.  很详细
作者: 悠然丶    时间: 2014-4-16 23:15
^o（孤8o|狼i¤F 发表于 2014-4-16 22:36
public static void main(String[] args) {

        System.out.println(digui(1)+1);

    sum += num*num + digui(num-1);
应该是sum = num *num +digui(num-1);吧
作者: ^o（孤8o|狼i¤F    时间: 2014-4-16 23:16
Ricky_Nick 发表于 2014-4-16 22:54
你这个每一次递归，都会把sum重新初始化为0

不是啊
当你在main 中调用的时候会
都会把sum 赋值为0
但是在递归调用中sum = 0 只有一次
作者: doyxy    时间: 2014-4-16 23:43
写了一个,不过看了地板感觉地板的更简单一点
  1. public class temp {

  3.         /**
  4.          * @param args
  5.          */
  6.         public static void main(String[] args) {
  7.                 // TODO Auto-generated method stub
  8.                 // 用递归求1-n每个数字的平方的和
  9.                 System.out.println(getPowerSum(5));
  10.         }

  12.         private static int getPowerSum(int i) {
  13.                 // TODO Auto-generated method stub
  14.                 int sum = i * i;
  15.                 System.out.println("sum:" + sum + " i:" + i);
  16.                 if (i > 1)
  17.                         sum += getPowerSum(i - 1);
  18.                 return sum;
  19.         }

  21. }
复制代码
作者: 马上都有    时间: 2014-4-17 00:04
class  aa
{
        public static void main(String[] args)
        {
                int h=count(4,0);
                System.out.println(h);
        }

        public static int count(int n,int m)
        {
                if(n!=0)
                {
                        m=n*n--;
                        //n--;
                        m+=count(n,m);
                }
                return m;
        }
}

/*
最简单的一个小例子：
递归的意思就是不断的调用自身的方法直到方法停止条件满足，然后从后面一个个方法结束。

打个比喻，有一栋楼房，一层表示一个方法，我们要站在最高处，没有向上爬的路了表示程序的停止条件。
我们要去最高处，我们就一层一层的往上爬，直到爬到了最顶层没有了向上爬的路，我们的目的也就达到了，我们又一层一层的往回走到原位，我们刚走出那层，那层也被炸掉了。
这就是一个递归流程，相当于从第一层爬到顶，没有向上的路，绝路了，再从顶层回到第一层每下一层就炸掉一层。
*/
作者: 张志成    时间: 2014-4-17 01:22
1*1 + 2*2 + 3*3 + … + n*n
public class Sum{
   public static void main(String[] args){
                      int sum= count(n);
                   System.out.println(sum);  }
public static int count(int n) {
               if(n==1){
                  return 1;   }
              int result=n*n+count(n-1);
                   return   result ; }
}
作者: 张志成    时间: 2014-4-17 01:26
张志成 发表于 2014-4-17 01:22
1*1 + 2*2 + 3*3 + … + n*n
public class Sum{
   public static void main(String[] args){

首先要考虑递归的结束条件,
作者: Ricky_Nick    时间: 2014-4-17 13:12
^o（孤8o|狼i¤F 发表于 2014-4-16 23:16
不是啊
当你在main 中调用的时候会
都会把sum 赋值为0

不好意思，重新看了一下，你这样也可以。。。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2