本篇文章给大家谈谈递归方法，以及递归方法求最大公约数对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。

本文目录一览：

• 1、C语言什么是递归
• 2、C语言什么是递归方法？
• 3、《算法导论》三种解递归式的方法
• 4、递归算法是什么？
• 5、三次递归怎么做

C语言什么是递归

递归方法的概念

类方法成员间允许相互调用，也可以自己调用自己。类的方法如果在方法体内直接或间接地自己调用自己就称为递归方法。

递归基本思想就是“自己调用自己”。递归方法实际上体现了“依此类推”、“用同样的步骤重复”这样的思想，它可以用简单的程序来解决某些复杂的计算问题。

递归调用在完成阶乘运算、级数运算、幂指数运算等方面特别有效。

在执行递归操作时，C#语言把递归过程中的信息保存在堆栈中。如果无限循环地递归，或者递归次数太多，则产生“堆栈溢出”错误

例：用递归方法求阶乘。利用的数学公式为n!=n*(n-1)!。当n=0时，n!=1。

代码如下：

public long F(int n)

{

if (n==1)

return 1;

else

return n*F(n-1);

}

C语言什么是递归方法？

编程里面估计最让人摸不着头脑的基本算法就是递归了。很多时候我们看明白一个复杂的递归都有点费时间，尤其对模型所描述的问题概念不清的时候，想要自己设计一个递归那么就更是有难度了。今天我也花费了半个小时来搞明白二叉树的平衡性的递归模型，首先我不明白什么叫做平衡性，所以花费的时候大部分实在试探理解平衡性的含义。在搞明白的时候，我突然想到假如让我来设计，在我知道平衡性的前提下，我是否可以建立如此简洁的递归模型。为此，我遇到的问题是我们到底在什么情况下适用递归模型，并且递归模型如何建立。

数学都不差的我们，第一反应就是递归在数学上的模型是什么。毕竟我们对于问题进行数学建模比起代码建模拿手多了。 （当然如果对于问题很清楚的人也可以直接简历递归模型了，运用数模做中介的是针对对于那些问题还不是很清楚的人）

自己观察递归，我们会发现，递归的数学模型其实就是归纳法，这个在高中的数列里面是最常用的了。回忆一下归纳法。

归纳法适用于想解决一个问题转化为解决他的子问题，而他的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。当然有一个是例外的，也就是递归结束的哪一个处理方法不适用于我们的归纳处理项，当然也不能适用，否则我们就无穷递归了。这里又引出了一个归纳终结点以及直接求解的表达式。如果运用列表来形容归纳法就是：

步进表达式：问题蜕变成子问题的表达式

结束条件：什么时候可以不再是用步进表达式

直接求解表达式：在结束条件下能够直接计算返回值的表达式

逻辑归纳项：适用于一切非适用于结束条件的子问题的处理，当然上面的步进表达式其实就是包含在这里面了。

这样其实就结束了，递归也就出来了。

递归算法的一般形式：

void func( mode)

{   

    if(endCondition)

    {

       constExpression       //基本项  

    }   

    else

        {

            accumrateExpreesion /归纳项

            mode=expression //步进表达式

            func(mode) / /调用本身，递归

        } 

}

最典型的就是N！算法，这个最具有说服力。理解了递归的思想以及使用场景，基本就能自己设计了，当然要想和其他算法结合起来使用，还需要不断实践与总结了。

例如：返回一个二叉树的深度：

int depth(Tree t){ 

if(!t) return 0; 

else { 

         int a=depth(t.right); 

         int b=depth(t.left); 

         return (ab)?(a+1):(b+1); 

    } 

}

判断一个二叉树是否平衡：

int isB(Tree t){ 

    if(!t) return 0; 

    int left=isB(t.left); 

    int right=isB(t.right); 

    if( left =0  right =0  left - right = 1 || left -right =-1) 

         return (leftright)? (right +1) : (left + 1); 

    else return -1; 

}

上面这两个递归的难易程度就不一样了，第一个关于深度的递归估计只要了解递归思想的都可以短时间设计出来，但第二个估计就要长点时间了。纯递归问题的难易主要纠结于一些条件表达式的构造以及初值的设置（上面的为直接表达式值的设定）。

最后需要补充的是，很多不理解递归的人，总认为递归完全没必要，用循环就可以实现，其实这是一种很肤浅的理解。因为递归之所以在程序中能风靡并不是因为他的循环，大家都知道递归分两步，递和归，那么可以知道递归对于空间性能来说，简直就是造孽，这对于追求时空完美的人来说，简直无法接接受，如果递归仅仅是循环，估计现在我们就看不到递归了。递归之所以现在还存在是因为递归可以产生无限循环体，也就是说有可能产生100层也可能10000层for循环。例如对于一个字符串进行全排列，字符串长度不定，那么如果你用循环来实现，你会发现你根本写不出来，这个时候就要调用递归，而且在递归模型里面还可以使用分支递归，例如for循环与递归嵌套，或者这节枚举几个递归步进表达式，每一个形成一个递归。

《算法导论》三种解递归式的方法

代入法可以用来确定一个递归式的上界或下界。这种方法很有效，但只能用于解的形式很容易猜的情形。

例如，我们需要确定下面递归式的上界：

该递归式与归并排序相似，我们可以猜测其解为

代入法要求证明，恰当选择常数 c0，可有 T(n)≤cn lgn。首先假设此上界对所有正数 mn 都成立，特别是对于 m=n/2，有 T(n/2)≤c(n/2)lg(n/2)。将其代入递归式，得到：

其中，只要 c≥1，最后一步都会成立。

并不存在通用的方法来猜测递归式的正确解，但总有一些试探法可以帮助做出好的猜测：

如果某个递归式与先前见过的类似，则可猜测该递归式有类似的解。如，递归式

看起来比较难解，因为右式 T 的自变量中加了 17，但我们可以猜测这个多出来的项对解的影响不大，因为当 n 很大时， 与 之间的差别并不大，两者都将 n 分成均匀的两半。

另一种方法是先证明递归式的较松的上下界，然后再缩小不确定性区间。例如，对递归式 ，因为递归式中有 n，而我们可以证明初始上界为 。然后，逐步降低其上界，提高其下界，直到达到正确的渐近确界 。

有时，我们或许能够猜出递归式解的渐近界，但却会在归纳证明时出现一些问题。通常，问题出在归纳假设不够强，无法证明其准确的界，遇到这种情况时，可以去掉一个低阶项来修改所猜测的界，以使证明顺利进行。如下面的递归式：

可以猜测其解为 ，即要证明对适当选择的 c，有 。有所猜测的界对递归式做替换，得到

由此无法得到 ，无论 c 的值如何。如果猜测一个更大的界，如 ，虽然这确实是上界，但事实上，所猜测的解 却是正确的。为了证明这一点，要做一个更强的归纳假设。

从直觉上说，猜测 几乎是正确的，只是差了一个常数 1，即一个低阶项，然而，就因为差了一项，数学归纳法就无法证明出期望的结果。从所作的猜测中减去一个低阶项，即 是个常数。现在有

只要 b≥ 1。这里，c 要选的足够大，以便能处理边界条件。

你可能会觉得从所作的猜测中减去一项有点儿与直觉不符。为什么不是增加一项来解决问题呢？关键在于要理解我们是在用数学归纳法：通过对更小的值作更强的假设，就可以证明对某个给定值的更强的结论。

在运用渐近表示时很容易出错。例如，对递归式 ，由假设 ，并证明

就是错误的，因为 c 是常数，因而错误地证明了 。错误在于没有证明归纳假设的准确形式，即 。

有时，对一个陌生的递归式作一些简单的代数变换，就会使之变成读者较熟悉的形式。如下例子：

这个式子看上去比较难，但可以对它进行简化，方法是改动变量。为了方便起见，不考虑数的截取整数问题，如将 化为整数。设 ，得

再设 ，得到新的递归式

这个式子看起来与 就非常像了，这个新的递归式的界是： 。将 带回 ，有 。

有时候，画出一个递归树是一种得到好猜测的直接方法。在递归树中，每一个节点都代表递归函数调用集合中一个子问题的代价。将树中每一层内的代价相加得到一个每层代价的集合，再将每层的代价相加，得到的结果是所有层次的总代价。当用递归式表示分治算法的运行时间时，递归树的方法尤其有用。

递归树最适合用来产生好的猜测，然后用代入法加以验证。但使用递归树产生好的猜测时，通常可以容忍小量的“不良量”，因为稍后就会证明所做的猜测。如果画递归树时非常地仔细，并且将代价都加了起来，那么就可以直接用递归树作为递归式的解的证明。

在讲述例子之前，我们先来看一个几何级数公式

对于实数 x≠1，式

是一个几何级数（或称指数级数），其值为

当和是无限的且 |x|1 时，有无限递减几何级数

我们以递归式

为例来看一下如何用递归树生成一个好的猜测。首先关注如何寻找解的一个上界，因为我们知道舍入对求解递归式通常没有影响（此处即是我们需要忍受不精确的一个例子），因此可以为递归式

创建一颗递归树，其中已将渐近符号改写为隐含的常数系数 c0。

构造的递归树如下：

求所有层次的代价之和，确定整棵树的代价：

最后的这个公式看起来不够整洁，但我们可以再次充分利用一定程度的不精确，并利用无限递减几何级数作为上界。回退一步，得到：

此时，我们得到了递归式的一个猜测，在上面的例子里， 系数形成了一个递减的等比级数，可知这些系数的总和的上界是常数 。由于树根所需的代价为 ，所以根部的代价占总代价的一个常数部分。换句话说，整棵树的总代价是由根部的代价所决定的。

事实上，如果 确实是此递归式的上界，那么它一定是确界，为什么呢？第一个递归调用所需要的代价是 ，所以 一定是此递归式的下界。

现在我们可以使用代换法来验证猜测的正确性， 是递归式 的一个上界。只需要证明，当某常数 d0， 成立。适用与前面相同的常数 c0，有

只要 d≥ ，最后一步都会成立。

上图是递归式

对应的递归树。我们还是使用 c 来代表 项常数因子。当将递归树内各层的数值加起来时，可以得到每一层的 cn 值。从根部到叶子的最长路径是 。因为当 时， ，所以树的深度是 。

直觉上，我们预期递归式的解至多是层数乘以每层的代价，也就是 。总代价被均匀地分布到递归树内的每一层上。这里还有一个复杂点：我们还没有考虑叶子的代价。如果这棵树是高度为 的完整二叉树，那么有 个叶子节点。由于叶子代价是常数，因此所有叶子代价的总和为 ，或者说 。然而，这棵递归树并不是完整的二叉树，少于 个叶子，而且从树根往下的过程中，越来越多的内部结点在消失。因此，并不是所有层次都刚好需要 cn 代价；越靠近底层，需要的代价越少。我们可以计算出准确的总代价，但记住我们只是想要找出一个猜测来使用到代入法中。让我们容忍这些误差，而来证明上界为 的猜测是正确的。

事实上，可以用代入法来证明 是递归式解的上界。下面证明 ，当 d 是一个合适的正值常数，则

上式成立的条件是 。因此，没有必要去更准确地计算递归树中的代价。

主方法给出了求解递归式的“食谱”方法，即将规模为 n 的问题划分为 a 个子问题的算法的运行时间，每个子问题规模为 ，a 和 b 是正常数。a 个子问题被分别递归地解决，时间各为 。划分原问题和合并答案的代价由函数 描述。

从技术正确性角度来看，递归式实际上没有得到很好的定义，因为 可能不是一个整数。但用 向上取整或向下取整来代替 a 项 并不影响递归式的渐近行为，因而，在写分治算法时略去向下取整和向上取整函数会带给很大的方便。

其中我们将 n/b 解释为 n 除以 b 的向下取整或向上取整。那么 T(n) 有如下渐近界：

在使用主定理之前，我们需要花一点时间尝试理解它的含义。对于三种情况的每一种，将函数 f(n) 与函数 进行比较。直觉上，两个函数较大者决定了递归式的解。若函数 更大，如情况 1，则解为 T(n)= ( )。若函数 f(n) 更大，如情况 3，则解为 T(n)= (f(n))。若两个函数大小相当，如情况 2，则乘上一个对数因子，解为 T(n)= ( )= ( )。

另外还有一些技术问题需要加以理解。在第一种情况下，不仅要有 小于 ，还必须是多项式地小于，也就是说， 必须渐近小于 ，要相差一个因子 ，其中 是大于 0 的常数。在第三种情况下，不是 大于 就够了，而是要多项式意义上的大于，而且还要满足“正则”条件 。

注意：三种情况并没有覆盖所有可能的 f(n)。当 f(n) 只是小于 但不是多项式地小于时，在第一种情况和第二种情况之间就存在一条“沟”。类似情况下，当 f(n) 大于 ，但不是多项式地大于时，第二种情况和第三种情况之间就会存在一条“沟”。如果 f(n) 落在任一条“沟”中，或是第三种情况种规则性条件不成立，则主方法就不能用于解递归式。

使用主方法很简单，首先确定主定理的哪种情况成立，即可得到解。

例如：

对于这个递归式，我们有 a=9，b=3，f(n)=n，因此 = = 。由于 f(n) = ，其中 ， 因此可以应用于主定理的情况 1，从而得到解 T(n) = Θ( ) 。

现在考虑

其中，a = 1， b = 3/2， f(n) = 1，因此 = = = 1 。由于 f(n) = = Θ(1) ，因此可应用于情况2，从而得到解 T(n) = Θ( ) 。

对于递归式

我们有 a = 3，b = 4，f(n) = nlgn，因此 = =O( )。由于 当 n，其中 ，因此，如果可以证明正则条件成立，即应用于情况 3。当 n 足够大时，对于 ， ，因此，由情况 3，递归式的解为 T(n)= ( )。

主方法不能用于如下递归式：

虽然这个递归式看起来有恰当的形式：a=2，b=2， ，以及 。你可能错误地认为应该应用情况 3，因为 渐近大于 。问题出现在它并不是多项式意义上的大于。对任意正常数 ，比值 都渐近小于 。因此，递归式落入了情况 2 和情况 3 之间的间隙。

证明分为两部分。第一部分分析“主”递归式 ，并作了简化假设 仅定义在 b1 的整数幂上，即 ， ， ，…。这部分从直觉上说明该定理为什么是正确的。第二部分说明如何将分析扩展至对所有的正整数 n 都成立，主要是应用数学技巧来解决向下取整函数和向上取整函数的处理问题。

取正合幂时的证明

对于递归式

此时的假设是 n 为 b1 的正合幂，且 b 不必是整数。分析可分成三个引理说明，第一个引理是将解原递归式的问题归约为对一个含和式的求值的问题。第二个引理决定含和式的界，第三个引理把前两个合在一起，证明当 n 为 b 的正合幂时主定理成立。

引理一 ：设 a≥1，b1 为常数，f(n) 为定义在 b 的正合幂上的非负函数。定义 如下：

其中 i 是正整数，则有

证明：如下图。根节点代价为 f(n)，它有 a 个子女，每个代价是 。（为方便起见可将 a 视为整数，但这对数学推导没什么影响。）每个子女又各有 a 个子女，代价为 。这样就有 个结点离根的距离为 2。一般地，距根为 j 的结点有 个，每一个的代价为 。每一个叶结点的代价为 ，每一个都距根 ，因为 。树中共有 个叶结点。

可以将树中各层上的代价加起来而得到方程 ，第 j 层上内部结点的代价为 ，故各层内部结点的总代价和为

在其所基于的分治算法中，这个和值表示了将问题分解成为子问题并将子问题的解合并时所花的代价，所有叶子的代价（即解 个规模为 1 的子问题的代价）为 。

根据递归树，主定理的三种情况对应于树中总代价的三种情况：1、由所有叶子节点的代价决定；2、均匀分布在各层上；3、由根结点的代价决定。

引理二 ：设 a≥1，b≥1 为常数， 为定义在 b 的整数幂上的非负函数。函数 由下式定义

对 b 的整数幂，该函数可被渐近限界为：

证明：对情况 1，有 ，这隐含着 。用它对方程 做代换，得

对 O 标记内的式子限界，方法是提出不变项并作简化，得到一个上升几何级数：

因为 b 与 都是常数，最后的表达式可化简为 。用此表达式对 作替换，得

情况 1 得以验证。

为证情况 2，假设 ，有 。用此式对方程 作替换，得

对 记号中的式子做类似情况 1 中的限界，但所得并非是几何级数，而是每项都是相同的:

用此方程对 中的和式做替换，有

则情况 2 得以验证。情况 3 也可以用类似的方式证明。

引理三 ：设 a≥1，b1 是常量， 是定义在 b 的整数幂上的非负函数。定义 T(n) 如下：

其中 i 是正整数。对于 b 的整数幂，T(n) 可有如下渐近界：

证明：用引理二给出的界来对引理一中的式 求值。对情况 1 有

对情况 2 有

对情况 3 有

递归算法是什么？

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。

递归程序

在支持自调用的编程语言中，递归可以通过简单的函数调用来完成，如计算阶乘的程序在数学上可以定义为：

这一程序在Scheme语言中可以写作：

(define (factorial n)  (if (= n 0)      1      (* n (factorial (- n 1)))))

不动点组合子

即使一个编程语言不支持自调用，如果在这语言中函数是第一类对象（即可以在运行期创建并作为变量处理），递归可以通过不动点组合子（英语：Fixed-point combinator）来产生。以下Scheme程序没有用到自调用，但是利用了一个叫做Z 算子（英语：Z combinator）的不动点组合子，因此同样能达到递归的目的。

(define Z  (lambda (f)    ((lambda (recur) (f (lambda arg (apply (recur recur) arg))))     (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact  (Z (lambda (f)       (lambda (n)         (if (= n 0)             1             (* n (f (- n 1))))))))

这一程序思路是，既然在这里函数不能调用其自身，我们可以用 Z 组合子应用(application)这个函数后得到的函数再应用需计算的参数。

尾部递归

尾部递归是指递归函数在调用自身后直接传回其值，而不对其再加运算。尾部递归与循环是等价的，而且在一些语言（如Scheme中）可以被优化为循环指令。 因此，在这些语言中尾部递归不会占用调用堆栈空间。以下Scheme程序同样计算一个数字的阶乘，但是使用尾部递归：

(define (factorial n)  (define (iter product counter)    (if ( counter n)        product        (iter (* counter product)              (+ counter 1))))  (iter 1 1))

能够解决的问题

数据的定义是按递归定义的。如Fibonacci函数。

问题解法按递归算法实现。如Hanoi问题。

数据的结构形式是按递归定义的。如二叉树、广义表等。

参考资料

百科-递归算法.百度百科[引用时间2018-4-2]

三次递归怎么做

递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。

一个过程(或函数)直接或间接调用自己本身，这种过程（或函数）叫递归过程（或函数）。

递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。

特点

递归算法是一种直接或者间接地调用自身算法的过程。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。

递归算法解决问题的特点：

(1) 递归就是在过程或函数里调用自身。

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

要求

递归算法所体现的“重复”一般有三个要求：

一是每次调用在规模上都有所缩小(通常是减半)；

二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；

三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。