第07章--函数概要.ppt

* * * * * * * * * * * * * * 显然这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且，每一个人的年龄都比其前一个人的年龄大2岁。见下页： * 从上图中可以看出，求解过程可分为两个阶段来完成：第一阶段是“回推”， 即将第n个人的年龄表示为第（n-1）个人年龄的函数，而第(n-1)个人的年龄仍然不知道，还要“回推”到第(n-2)个人的年龄… … ，直到第一个人的年龄。此时age(1)已知，不必向前推了。然后开始第二个阶段，采用递推的方法，也就是从第1 个人的已知年龄推算出第2个人的年龄，从第2个人的年龄再推算出第3个人的年龄… … ，一直推算出第5个人的年龄（18岁）为止。也就是说，一个递归的问题可以分为“回推”和“递推”两个阶段。而且要经历许多步才能求出最后的值。 显而易见，如果要求递归过程不是无限制进行下去，就必须有一个结束递归过程条件。例如，象age(1)=10就是一个递归条件。 * 从上图中可以看到，age函数共计被调用了5次。其中age(5) 是main函数调用的，其余4次是在age 函数中调用的，即递归调用4次。 在此处应强调的是：在某一次调用age函数时并不是立即得到age(n)的值，而是一次又一次地进行递归调用，到age(1)时才有确定的值，然后再递推出age (2)、age(3)、age(4)、age(5)。 * 显然这是一个递归问题。要求第5个人的年龄，就必须先知道第4个人的年龄，而第4个人的年龄也不知道，要求第4个人的年龄必须先知道第3个人的年龄，而第3个人的年龄又取决于第2个人的年龄，第2个人的年龄取决于第1个人的年龄。而且，每一个人的年龄都比其前一个人的年龄大2岁。见下页： * 从上图中可以看到，age函数共计被调用了5次。其中age(5) 是main函数调用的，其余4次是在age 函数中调用的，即递归调用4次。 在此处应强调的是：在某一次调用age函数时并不是立即得到age(n)的值，而是一次又一次地进行递归调用，到age(1)时才有确定的值，然后再递推出age (2)、age(3)、age(4)、age(5)。 现在换一个角度考虑问题，ｎ! 不仅是 1*2*3* ... *n 还可以定义成 n! = 当 n=0 n*(n-1)! 当 n0 按照该定义，ｎ! 就是一个简单的条件语句和表达式计算，可以编出如下函数： float factorial ( int n ) { if ( n==0 ) return 1; else return n*factorial(n-1); } 问题：在函数 factorial 内又调用函数 factorial 本身，行吗？ 回答：行！ 首先按作用域规则，在函数 factorial 内又调用函数 factorial 本身是合法的；其次 C 系统保证上述调用过程执行的正确性，这就是递归。 从静态行文角度看，在定义一个函数时，若在定义它的内部，又出现对它本身的调用，则称该函数是递归的，或递归定义的。 从动态执行角度看，当调用一个函数时，在进入相应函数，还没退出（返回）之前，又再一次的调用它本身，而再一次进入相应函数，则称之为递归，或称之为对相应函数的递归调用。 称递归定义的函数为递归函数。上述函数 factorial 就是递归函数。若计算 5! ，使用函数调用factorial(5) ，观察其计算过程: return 5*f(4) f(5) f=120 f(4) f(3) f(2) f(1