黑马程序员技术交流社区

标题: 关于递归和数组的一些问题 [打印本页]
作者: Leo_yeung    时间: 2013-8-15 22:59
标题: 关于递归和数组的一些问题
本帖最后由 Leo_yeung 于 2013-8-20 00:57 编辑

如下递归函数用来打印数组value的前i个元素，函数PrintArray()中没有for循环，但是为什么打印数组的时候是从value[0]到value[9]的，还有i是从0开始到10循环的，因为如果在if语句中打印i的值，会打印0，所以说明i从0开始；最后为value[9]，所以结束于10；对于递归的概念还有点模糊，谁能帮我分析以下程序的执行过程。

class Rec{

        int value[];
        Rec(int i){
                value=new int;
        }
        void PrintArray(int i){
                if(i==0){
                        return;}
                else PrintArray(i-1);
                System.out.println("["+(i-1)+"]"+value[i-1]);
        }
}
class RecTest{
        public static void main(String args[]){
                Rec ob=new Rec(10);
                int j;
                for(j=0;j<10;j++)
                        ob.value[j]=j;
                ob.PrintArray(10);
        }
}

作者: 黑马-张明    时间: 2013-8-16 10:05
程序调用自身的编程技巧称为递归（ recursion）。递归是一种非常有用的算法，在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。
递归必须要满足三个条件：一是边界条件；二是递归前进段；三是递归返回段。
递归算法要注意的两点：
      (1) 递归就是在方法里调用自己;
      (2) 在使用递归算法时，必须要有一个明确的递归结束条件，称为递归出口。
先看一个简单的例子，求从1加到5的和，代码如下：
  1. package com.juziku;

  3. /**
  4. * 递归测试
  5. * @author sunlightcs
  6. * 2011-3-9
  7. * http://hi.juziku.com/sunlightcs/
  8. */
  9. public class RecursionTest {
  10.        
  11.         /**
  12.          * 求从1加到n的和
  13.          */
  14.         public static int sum(int n){
  15.                 if(n == 1){
  16.                         return 1;
  17.                 }else{
  18.                         return n + sum(n-1);
  19.                 }
  20.         }
  21.        
  22.        
  23.         public static void main(String[] args) {
  24.                 System.out.println(sum(5));
  25.         }
  26. }
复制代码
先分析一下执行的流程：
n=5时，执行sum(5)方法，返回的结果为：5 + sum(4)
n=4时，执行sum(4)方法，返回的结果为：4 + sum(3)
n=3时，执行sum(3)方法，返回的结果为：3 + sum(2)
n=2时，执行sum(2)方法，返回的结果为：2 + sum(1)
n=1时，执行sum(1)方法，返回的结果为：1

再向上返回，依次执行：
2+1
3+(2+1)
4+(3+2+1)
5+(4+3+2+1) = 15

思路应该是这样的：
要知道从1加到5的和，先得知道从1加到4的和，即：5+sum(4)
要知道从1加到4的和，先得知道从1加到3的和，即：4+sum(3)
要知道从1加到3的和，先得知道从1加到2的和，即：3+sum(2)
要知道从1加到2的和，先得知道从1加到1的和，即：2+sum(1)
从而很容易看出，递归的出口为1也就是sum(1)的值为1

再看一个例子，求5的阶乘，代码如下：
  1. package com.juziku;

  3. /**
  4. * 递归测试
  5. * @author sunlightcs
  6. * 2011-3-8
  7. * http://hi.juziku.com/sunlightcs/
  8. */
  9. public class RecursionTest {

  11.         /**
  12.          * 求n的阶乘
  13.          */
  14.         public static int multiply(int n) {
  15.                 if(n == 1){
  16.                         return 1;
  17.                 }else{
  18.                         return n * multiply(n - 1);
  19.                 }
  20.         }
  21.        
  22.        
  23.         public static void main(String[] args) {
  24.                 System.out.println(multiply(5));
  25.         }
  26. }
复制代码
思路跟上面是一样的
作者: kmter    时间: 2013-8-17 00:22
本帖最后由 kmter 于 2013-8-17 00:23 编辑

本来是准备画一张解析图给你解释一下的, 画一半时发现一个更好的方法,添加两行"测试代码".如下:
  1. class Rec{
  2.         int value[];
  3.         Rec(int i){
  4.                 value=new int[i];
  5.         }
  6.         void PrintArray(int i){
  7.                 if(i==0){
  8.                         System.out.println("return");                // 表示return执行
  9.                         return;
  10.                 } else {
  11.                         System.out.println("PrintArray[i], i=" + i);                //在调用函数本身之前输出当前PrintArray方法参数i的值
  12.                         PrintArray(i-1);
  13.                 }
  14.                 System.out.println("["+(i-1)+"]"+value[i-1]);
  15.         }
  16. }
  17. class RecTest{
  18.         public static void main(String args[]){
  19.                 Rec ob=new Rec(10);
  20.                 int j;
  21.                 for(j=0;j<10;j++)
  22.                         ob.value[j]=j;
  23.                 ob.PrintArray(10);
  24.         }
  25. }
复制代码
你测试运行一下, 查看打印结果就可以大致了解一下PrintArray方法是怎样运行的了, 对你对递归的了解应该有所帮助
作者: Leo_yeung    时间: 2013-8-17 01:11
谢谢各位的指点，似乎明白了；递归开始时顺序执行的，最后是逆序执行的；分析开始写的程序，加了两行打印信息后，豁然开朗；i不为0时就继续调用函数自身：
i=10,PrintArray(10-1)
i=9,PrintArray(9-1)
i=8,PrintArray(8-1)
...
i=1,PrintArray(1-1)
此时i=0,return;
然后递归函数以i=1为出口输出：即
[0] 0
...
[9] 9




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