Javascript函数声明与递归调用 2
Javascript函数声明与递归调用
Javascript的函数的声明方式和调用方式已经是令人厌倦的老生常谈了，但有些东西就是这样的，你来说一遍然后我再说一遍。每次看到书上或博客里写的Javascript函数有四种调用方式，我就会想起孔乙己：茴字有四种写法，你造吗？
AD：
Javascript的函数的声明方式和调用方式已经是令人厌倦的老生常谈了，但有些东西就是这样的，你来说一遍然后我再说一遍。每次看到书上或博客里写的Javascript函数有四种调用方式，我就会想起孔乙己：茴字有四种写法，你造吗？
尽管缺陷有一堆，但Javascript还是令人着迷的。Javascript众多优美的特性的核心，是作为顶级对象（first-class objects）的函数。函数就像其他普通对象一样被创建、被分配给变量、作为参数被传递、作为返回值以及持有属性和方法。函数作为顶级对象，赋予了Javascript强大的函数式编程能力，也带来了不太容易控制的灵活性。
1、函数声明
变量式声明先创建一个匿名函数，然后把它赋值给一个指定的变量：
varf=function(){functionbody};
通常我们不必关心等号右边表达式的作用域是全局还是某个闭包内，因为它只能通过等号左边的变量f来引用，应该关注的是变量f的作用域。如果f指向函数的引用被破坏（f = null），且函数没有被赋值给任何其它变水草玛瑙 https://www.wendangku.net/doc/8c3479887.html,量或对象属性，匿名函数会因为失去所有引用而被垃圾回收机制销毁。
也可以使用函数表达式创建函数：
functionf(){functionbody}
与变量式不同的是，这种声明方式会为函数的一个内置属性name赋值。同时把函数赋值给当前作用域的一个同名变量。（函数的name属性，configurable、enumerable和writable均为false）functionf(){functionbody} console.log(https://www.wendangku.net/doc/8c3479887.html,); f console.log(f);f()
Javascript变量有一个的特别之处，就是会把变量的声明提前，表达式式的函数声明，也会把整个函数的定义前置，因此你可以在函数定义之前使用它：
console.log(https://www.wendangku.net/doc/8c3479887.html,); f console.log(f);f() functionf(){functionbody}
函数表达式的声明会被提升到作用域顶层，试试下面的代码，它们不是本文的重点：
vara=0; console.log(a);0ora()? functiona(){}
Crockford建议永远使用第一种方式声明函数，他认为第二种方式放宽了函数必须先声明后使用的要求从而会导致混乱。（Crockford是一个类似于罗素口中用来比喻维特根斯坦的有良心的艺术家那样的有良心的程序员，这句话很拗口吧）
函数式声明
functionf(){}
看起来是
varf=functionf(){};
的简写。
而
vara=functionb(){};
的表达式，创建一个函数并把内置的name属性赋值为 b ，然后把这个函数赋值给变量a，你可以在外部使用a()来调用它，但却高山茶 https://www.wendangku.net/doc/8c3479887.html,不能使用b(），因为函数已被赋值给a，所以不会再自动创建一个变量b，除非你使用var b = a声明一个变量b。当然这个函数的name 是b 而不是a 。
使用Function构造函数也可用来创建函数：
varf=newFunction( a,b,c , returna+b+c; );
这种方式其实是在全局作用域内生成一个匿名函数，并把它赋值给变量f。
2、递归调用
递归被用来简化许多问题，这需要在一个函数体中调用它自己：
一个简单的阶乘函数varf=function(x){ if(x===1){ return1; }else{ returnx*f(x-1); } };
Javascript中函数的巨大灵活性，导致在递归时使用函数名遇到困难，对于上面的变量式声明，f是一个变量，所以它的值很容易被替换：
varfn=f; f=function(){};
函数是个值，它被赋给fn，我们期待使用fn(5)可以计算出一个数值，但是由于函数内部依然引用的是变量f，于是它不能正常工作了。
函数式的声明看起来好些，但很可惜：
functionf(x){ if(x===1){ return1; }else{ returnx*f(x-1); } } varfn=f; f=function(){};maybeenwarningbybrowser fn(5);NaN
看起来，一旦我们定义了一个递归函数，便须注意不要轻易改变变量的名字。
上面谈论的都是函数式调用，函数还有其它调用方式，比如当作对象方法调用。
我们常常这样声明对象：
varobj1={ num：5，fac：function(x){ functionbody } };
声明一个匿名函数并把它赋值给对象的属性（fac）。
如果我们想要在这里写一个递归，就要引用属性本身：
varobj1={ num:5, fac:function(x){ if(x===1){ return1; }else{ returnx*obj1.fac(x-1); } } };
当然，它也会遭遇和函数调用方式一样的问题：
varobj2={fac:obj1.fac}; obj1={}; obj2.fac(5);Sadness
方法被赋值给obj2的fac属性后，内部依然要引用obj1.fac，于是失败了。
换一种方式会有所改进：
varobj1={ num:5, fac:function(x){ if(x===1){ return1; }else{ returnx*this.fac(x-1); } } }; varobj2={fac:obj1.fac}; obj1={}; obj2.fac(5);ok
通过this关键字获取函数执行时的context中的属性，这样执行obj2.fac时，函数内部便会引用obj2的fac属性。
可是函数还可以被任意修改context来调用，那就是万能的call和apply：
obj3={}; obj1.fac.call(obj3,5);deadagain
于是递归函数又不能正常工作了。
我们应该试着解决这种问题，还记得前面提到的一种函数声明的方式吗？
vara=functionb(){};
这种声明方式叫做内联函数（inline function），虽然在函数外没有声明变量b，但是在函数内部，是可以使用b()来调用自己的，于是
varfn=functionf(x){ tryifyouwrite varf=0；here if(x===1){ return1; }else{ returnx*f(x-1); } }; varfn2=fn; fn=null; fn2(5);OK
hereshowthedifferencebetween varf=functionf(){} and functionf(){} varf=functionf(x){ if(x===1){ return1; }else{ returnx*f(x-1); } }; varfn2=f; f=null; fn2(5);OK
varobj1={ num:5, fac:functionf(x){ if(x===1){ return1; }else{ returnx*f(x-1); } } }; varobj2={fac:obj1.fac}; obj1={}; obj2.fac(5);ok varobj3={}; obj1.fac.call(obj3,5);ok
就这样，我们有了一个可以在内部使用的名字，而不用担心递归函数被赋值给谁以及以何种方式被调用。
Javascript函数内部的arguments对象，有一个callee属性，指向的是函数本身。因此也可以使用arguments.callee在内部调用函数：
functionf(x){ if(x===1){ return1; }else{ returnx*arguments.callee(x-1); } }
但arguments.callee是一个已经准备被弃用的属性，很可能会在未来的ECMAscript版本中消失，在ECMAscript 5中use strict 时，不能使用arguments.callee。
最后一个建议是：如果要声明一个递归函数，请慎用new Function这种方式，Function构造函数创建的函数在每次被调用时，都会重新编译出一个函数，递归调用会引发性能问题你会发现你的内存很快就被耗光了。
原文链接：JackSparrowblog222221
【编辑推荐】
构件中国：面向构件的方法与实践
本书通过丰富的案例研究示例，阐明了构建面向构件软件的最重要因素：概念、技术、规范、管理以及分析与设计过程。
本书的涵盖范
递归调用详解,分析递归调用的详细过程
递归调用详解，分析递归调用的详细过程 2009年05月23日星期六 22:52 一、栈 在说函数递归的时候，顺便说一下栈的概念。 栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行是系统自动处理。所谓的系统自动维护，实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们，但程序员应该对此有所了解。 再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时，运行时系统将把调用者的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时，系统把被调用者的自变量压入到栈中，并把栈指针再向下移，以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后，被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作，栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针，以他为参考，用正或负的偏移值来访问栈中的变量。当被调用者准备返回时，系统弹出栈中所有的自变量，这时栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回，系统从栈中弹出返回地址，调用者就可以继续执行了。当调用者继续执行时，系统还将从栈中弹出调用者的实参，于是栈指针回到了调用发生前的位置。 可能刚开始学的人看不太懂上面的讲解，栈涉及到指针问题，具体可以看看一些数据结构的书。要想学好编程语言，数据结构是一定要学的。 二、递归 递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级
函数的递归调用与分治策略
函数的递归调用与分治策 略 This manuscript was revised on November 28, 2020
函数的递归调用与分治策略 递归方法是算法和程序设计中的一种重要技术。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题。递归方法具有易于描述和理解、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。递归方法中所使用的“分而治之”的策略也称分治策略。 递归方法的构造 构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。下面由一个求n的阶乘的程序为例，总结出构造递归方法的一般步骤。 [例1]从键盘输入正整数N（0<=N<=20），输出N!。 [分析]N!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。 [步骤1]描述递归关系递归关系是这样的一种关系。设{U1,U2,U3,…,Un…}是一个序列，如果从某一项k开始，Un和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。 注意到，当N>=1时，N!=N*(N-1)!（N=1时，0!=1），这就是一种递归关系。对于特定的K!，它只与K与(K-1)!有关。 [步骤2]确定递归边界在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。 确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死
循环。例如以下程序： #include <> int f(int x){ return(f(x-1)); } main(){ cout<
实验7-2-函数调用
实验7-2 函数(二) 1 【实验目的】 （1）掌握函数的嵌套调用的方法 （2）掌握函数的递归调用的方法 （3）掌握全局变量和局部变量的概念和用法 【实验要求】 （1）熟练掌握函数的嵌套调用的方法 （2）熟练掌握函数的递归调用的方法 【实验环境】 (1) Microsoft XP操作系统 (2) Microsoft VC++ 6.0 【实验内容】 1、素数https://www.wendangku.net/doc/8c3479887.html,/acmhome/problemdetail.do?&method=showdetail&id=1098描述：输出100->200之间的素数的个数，以及所有的素数。 输入：无 输出：100->200之间的素数的个数，以及所有的素数。 样例输入：无 样例输出：
21 101 103 ... 197 199 2、字符串逆序https://www.wendangku.net/doc/8c3479887.html,/JudgeOnline/problem.php?id=1499 题目描述：写一函数，使输入的一个字符串按反序存放，在主函数中输入输出反序后的字符串。 输入：一行字符 输出：逆序后的字符串 样例输入：123456abcdef 样例输出：fedcba654321 3、字符串拼接https://www.wendangku.net/doc/8c3479887.html,/JudgeOnline/problem.php?id=1500 题目描述：写一函数，将两个字符串连接 输入：两行字符串 输出：链接后的字符串 样例输入： 123 abc 样例输出 123abc 4、输出元音https://www.wendangku.net/doc/8c3479887.html,/JudgeOnline/problem.php?id=1501
递归算法详解
递归算法详解 C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。 许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。 这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。 我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系： ‘0’+ 0 =‘0’ ‘0’+ 1 =‘1’ ‘0’+ 2 =‘2’ ... 从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。 这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。 我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。 这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。 在程序中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。 /*接受一个整型值（无符号0，把它转换为字符并打印它，前导零被删除*/
【习题】函数调用Word版
函数调用 【实验目的】： 1. 掌握函数的定义和调用方法。 2. 练习重载函数的使用。 3. 练习有默认参数值的函数的使用。 4. 练习使用系统函数。 5. 熟悉多文件工程结构。 【实验内容】： 1.编写函数int add(int x, int y)，实现两个整型数据x,y的求和功能。 ·要求：使用Visual C++的Debug调试功能，记录在函数调用时实参和形参的值 的变化。 2.编写一个求x的n次方的程序int pow(int m, int n)，计算m的n次方的结果。 3.利用上题中设计两个函数，设计一个求两个整数的平方和的程序。要求如下： a)主函数中调用求和函数: int add(int x, int y)；
求和函数add中调用上题设计的int pow(int m, int n)函数来计算其平方。 4.多文件程序结构：一个文件可以包含多个函数定义，但是一个函数的定义必须完 整的存在于一个文件中。要求： a)将add函数的声明部分放在头文件(add.h)中，实现部分放在源文件(add.cpp) 中。 b)将pow函数的声明部分放在头文件(pow.h)中，实现部分放在源文件(pow.cpp) 中。 c)在main函数中调用add函数，计算从屏幕终端输入的两个数据之和。(main 函数的实现在main.cpp中) 5.将第2题设计的pow函数修改成为递归函数。
6.设计一个函数int fac(int n)，利用函数的递归调用，来计算n！(n的阶乘)。 ·要求：单步调试程序，记录递归函数的调用过程。 7.使用系统函数pow(x,y)计算x y的值，注意包含头文件cmath。 8.从键盘输入两个数字，分别赋值给变量a、b，设计一个子函数swap，实现这两个数字交换次序。（注：根据需要自己设计函数的参数及返回值） ·要求：使用Visual C++的Debug调试功能，记录在函数调用时实参和形参的值的变化。 9.设计一个函数，求圆的面积。 要求：在主函数中调用子函数calArea计算圆的面积。并将calArea函数设计为内联函数。
第十一讲 函数的递归调用及函数中的变量定义
第十一讲函数的递归调用及函数中的变量定义 一、函数的递归调用 1．递归的概念 直接递归调用：调用函数的过程中又调用该函数本身，自己调用自己。 间接递归调用：调用f1函数的过程中调用f2函数，而f2中又需要调用f1。 以上均为无终止递归调用。为了让这种调用终止，一般要用if语句来控制使递归过程到某一条件满足时结束。 2、递归法 类似于数学证明中的反推法，从后一结果与前一结果的关系中寻找其规律性。 递归法：从结果出发，归纳出后一结果与前一结果直到初值为止存在的关系 编程思想：设计一个函数（递归函数），这个函数不断使用下一级值调用自身，直到结果已知处——选择控制结构 其一般形式是： 递归函数名f （参数n） { if (n=初值) 结果=常量； else 结果=含f(x-1)的表达式； return 结果； } 例1．输入一个n,编写函数求n!，根据不同的算法，我们可以用三种方式。 方式一：用递推算法，Sn=n!的递推关系如下： 1 （n=1,0） Sn= Sn-1×n n>1 是一种累计乘积的关系，先得到上一个数的阶乘，然后再得到得到下个数的阶乘，用循环结构来实现。 程序代码如下： main()
{ int n; float sn; float fac(int ); /*函数的声明*/ printf("Input n="); scanf("%d",&n); sn=fac(n); /*函数的调用*/ printf("%d!=%.0f",n,sn); } float fac(int n) /*函数的定义*/ { float f=1.0; int i; if (n==0||n==1) return f; for(i=1;i<=n;i++) f=f*i; return f; } 方式二：用递归算法，f(n)=n!的递归求解关系如下： 1 （n=1,0） f(n)= f(n-1)×n n>1 递归程序分两个阶段执行—— ①回推（调用）：欲求n! →先求 (n-1)! →(n-2)! →…→ 1! 若1！已知，回推结束。 ②递推（回代）：知道1！→2！可求出→3！→…→ n！ 注意：在此可画图来说明 程序清单如下： main() { int n; float sn; float fac(); /*函数的声明*/ clrscr(); printf("Input n=");
用递归法解决问题
3.5用递归法解决问题 【教材分析】 “用递归法解决问题”是《算法与程序设计》第三章第5节的内容，学业水平测试对本节内容也达到了B级要求，本节内容是在学习了VB基础知识中的三种基本结构，并且学习了数组、用解析法和穷举法解决问题等算法。本节先后介绍了“什么是递归法”、“自定义函数”、以及应用自定义函数结合递归算法来解决问题实例。通过本节内容的学习可以培养学生分析和分解问题的能力。从教材的结构上看“自定义函数”和“递归算法”是独立的，可以分别讲解，但在使用时两者是相辅相成的。 【学情分析】 这节课的教学对象是高中二年级学生，已经学习了算法与程序设计VB中的一些基础知识，初步了解了算法的概念。特点是在学习循环结构的过程中，学生已经积累了一些“递归”和“穷举”的算法。但是学生对函数尤其是“自定义函数”非常陌生，而“自定义函数”和“递归法”是本册的学习重点，也是以后编程的重点。学习本节内容学生可以充分体会递归算法的思想过程，扩大原来的知识面，进一步认识程序设计的功能，进一步激发学生学习算法与程序设计的兴趣。 【教学目标】 1．知识与技能： 理解什么是递归法，会用递归法的思想分析和解决问题 理解什么是自定义函数，能应用自定义函数实现递归算法的编程 2．过程与方法 学生通过思考、探究，体验递归算法和发现问题与解决问题的步骤 3．情感态度与价值观 在建立数学模型中培养学生的抽象思维能力，培养学生多维度思考问题和解决能力。 树立多学科整合的思想意识，能够用联系的观点解决问题。 【教学重点】 理解什么是递归算法，学会用递归法的思想分析问题。 理解自定义函数的概念。 【教学难点】 用自定义函数和递归算法编写程序解决问题 【教学方法及策略】
C语言递归
递归，作为C语言最经典的算法之一，是一种非常有用的程序设计方法。虽然用递归算法编写的程序结构清晰，具有很好的可读性，还往往使某些看起来不易解决的问题变得容易解决。但在递归函数中，由于存在着自调用过程，程序控制反复进入其自身，使程序的分析设计有一定困难，致使很多初学者往往对递归迷惑不解，也在这上面花了不少的时间，却收效甚微。那么，究竟什么是递归?怎么实现递归呢? 所谓递归，简而言之就是在调用一个函数的过程中又直接或间接地调用该函数本身，以实现层次数据结构的查询和访问。在函数中直接调用函数本身，称为直接递归调用。在函数中调用其它函数，其它函数又调用原函数，这就构成了函数自身的间接调用，称为间接递归调用。 而采用递归方法来解决问题，必须符合以下三个条件： 1、可以把要解决的问题转化为一个新问题，而这个新的问题的解决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减。 说明：解决问题的方法相同，调用函数的参数每次不同（有规律的递增或递减），如果没有规律也就不能适用递归调用。 2、可以应用这个转化过程使问题得到解决。 说明：使用其他的办法比较麻烦或很难解决，而使用递归的方法可以很好地解决问题 3、必定要有一个明确的结束递归的条件。 说明：一定要能够在适当的地方结束递归调用。不然可能导致系统崩溃。 好知道是这样以后;我们来写一个众多教材上的程序：使用递归的方法求n!。 当n>1时，求n!的问题可以转化为n*(n-1)!的新问题。比如n=4： 第一部分：4*3*2*1 n*(n-1)! 第二部分：3*2*1 (n-1)(n-2)! 第三部分：2*1 (n-2)(n-3)! 第四部分：1 (n-4)! 4-4=0，得到值1，结束递归。 我给的源程序如下： #include
C语言程序设计 递归调用的概念
7.3.1递归调用的概念 函数的递归调用指的是一个函数执行过程中出现了直接或间接调用函数本身的调用方式。如果直接调用函数本身称为直接递归；如果调用了另外一个函数，那个函数又调用该函数，则称为间接递归。 递归方法的基本思想是将一个问题向下分解具有同样解决方法但规模不断缩小的子问题，不断进行这样的分解，直到分解的子问题有一个已知解。下面通过一个例子来讲解递归的概念。 例如，某数列为k(n)的定义为： 1n=1 k(n)=2×k(n-1)n为偶数 3×k(n-1)n为奇数 求该数列的第四项k(4)。 从以上数列的定义来看，该数列的任何一项均受前一项的约束，在求解k(4)时，首先要求解k(3)，要求解k(3)就必须先知道k(2)的值，k(2)的值取决于k(1)的值。由于k(1)的值是已知的，然后再由k(1)反推回去计算k(2)，k(3)，k(4),得到K(4)的值。求解过程可以用图7-2表示。 k(4)=k(3)×2 k(3)=k(2)×3 k(2)=k(1)×2 k(1)=1k(2)=1×2=2 k(3)=2×3=6 k(4)=6×2=12 图7-2回推和递推过程 从图7-2可以看出，求解过程分为两个阶段：第一阶段是“回推”，将第4个值表示为第3个值的函数，将第3个值表示为第2个值的函数，再回推到第1个，而k(1)是已知的，到达了递归的边界。第二阶段使用“递推”，从已知的第1个值推出第2个值，从第2个值推出第3个值，从第3个值就推出了第4个值。整个的回推和递推过程就称为递归过程。 可以用一个函数描述上面的递归过程： int k(int n)/*递归计算函数*/ { int m;/*m存放函数的返回值*/ if(n==1)m=1; else if(n%2==0)m=k(n-1)*2;/*调用自身，n为偶数*/ else m=k(n-1)*3;/*调用自身，n为奇数*/ return(m);
函数的递归调用与分治策略
函数的递归调用与分治策略 递归方法是算法和程序设计中的一种重要技术。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题。递归方法具有易于描述和理解、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。递归方法中所使用的“分而治之”的策略也称分治策略。 递归方法的构造 构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。下面由一个求n的阶乘的程序为例，总结出构造递归方法的一般步骤。 [例1]从键盘输入正整数N（0<=N<=20），输出N!。 [分析]N!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。 [步骤1]描述递归关系递归关系是这样的一种关系。设{U1,U2,U3,…,Un…}是一个序列，如果从某一项k开始，Un和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。 注意到，当N>=1时，N!=N*(N-1)!（N=1时，0!=1），这就是一种递归关系。对于特定的K!，它只与K与(K-1)!有关。 [步骤2]确定递归边界在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。 确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序： #include 程序函数递归原理讲解 一、栈 在说函数递归的时候，顺便说一下栈的概念。 栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时，系统每次向栈中压入一个对象，然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时，最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的，它不需要程序员编写代码去维护，而是由运行是系统自动处理。所谓的系统自动维护，实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们，但程序员应该对此有所了解。 再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时，运行时系统将把调用者的所有实参和返回地址压入到栈中，栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时，系统把被调用者的自变量压入到栈中，并把栈指针再向下移，以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后，被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作，栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针，以他为参考，用正或负的偏移值来访问栈中的变量。当被调用者准备返回时，系统弹出栈中所有的自变量，这时栈指针移动了被调 用者刚开始执行时的位置。接着被调用者返回，系统从栈中弹出返回地址，调用者就可以继续执行了。当调用者继续执行时，系统还将从栈中弹出调用者的实参，于是栈指针回到了调用发生前的位置。 可能刚开始学的人看不太懂上面的讲解，栈涉及到指针问题，具体可以看看一些数据结构的书。要想学好编程语言，数据结构是一定要学的。 二、递归 递归，是函数实现的一个很重要的环节，很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身，或者在自己函数调用的下级函数中调用自己。 递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝，这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础，是使得递归成为可能。假定某个调用函数调用了一个被调用函数，再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。 程序员需保证递归函数不会随意改变静态变量和全局变量的值，以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程，并且返回到顶层。 函数递归调用讲解 一、函数调用与返回流程： 在一个函数中调用另一个函数时，程序控制即转入到被调用的函数中，在函数代码执行完成后，返回到主函数中的调用处继续执行主函数中的后续代码。见以下的程序： #include "Stdio.h" #include "Conio.h" int sub(int x) { int z; ...... return z; } int main(void) { ....... y=sub(x); ....... getch(); return 0; } 当主函数执行到y=sub(x)时，将变量x的值作为参数传递到函数sub的形式参数x中，程序控制转入到sub函数中；执行函数sub中的代码，遇到return z时，将变量z的值作为函数的结果值返回，程序控制转回到主函数main中继续执行其后的代码。如下图所示： 如果在函数sub中又调用了其他的函数如fun，则形成了函数的嵌套调用。 从上图中可以看到，函数调用是逐级调用、逐级返回的。即从函数fun中只能返回到函数sub中，而不能直接返回到函数main中。 二、递归调用 如果一个函数调用了这个函数自己，则形成递归调用。递归调用是一种特殊的嵌套调用，在调用与返回的流程上与函数嵌套调用没有区别。但由于函数调用自己，因此在理解上有一定的难度。 例：使用函数递归调用计算n!。阶乘计算的递推公式为： 0!=1,1!=1……n!=n*(n-1)! #include "Stdio.h" #include "Conio.h" int fun(int n) { int f; if(n==1||n==0) f=1; else f=n*fun(n-1); return f; } int main(void) { int x,p; scanf("%d",&x); p=fun(x); printf("%d",p); getch(); return 0; } 下图示出了当输入x=3时，函数调用与返回的情形。注意：在每一次调用函数fun时，变量n的值都是不同的。递归原理讲解
函数递归调用讲解