×

递归

什么是递归的概念？递归函数通常是用来解决什么问题的

admin admin 发表于2022-09-04 20:20:09 浏览105 评论0

抢沙发发表评论

本文目录

什么是递归的概念


1至100的和这个程序需要循环求sum=sum+i（i每次自增1）。没有用到递归，
1至100的和累积求值，递归调用是一个循环程序的调用
sum=sum+i只是C语言的一个实现的函数语句！
递归的基本概念和特点
程序调用自身的编程技巧称为递归（ recursion）。
一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。
一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
注意：
(1) 递归就是在过程或函数里调用自身;
(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。

递归函数通常是用来解决什么问题的


递归函数通常用来解决结构自相似的问题。所谓结构自相似，是指构成原问题的子问题与原问题在结构上相似，可以用类似的方法解决。具体地，整个问题的解决，可以分为两部分：第一部分是一些特殊情况，有直接的解法；第二部分与原问题相似，但比原问题的规模小。实际上，递归是把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的问题，直至每个小问题都可以直接解决。因此，递归有两个基本要素：
　　（1）边界条件：确定递归到何时终止，也称为递归出口。
　　（2）递归模式：大问题是如何分解为小问题的，也称为递归体。递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
　　递归就是某个函数直接或间接地调用了自身，这种调用方式叫做递归调用。说白了，还是函数调用。既然是函数调用，那么就有一个雷打不动的原则：所有被调用的函数都将创建一个副本，各自为调用者服务，而不受其他函数的影响。

c++中什么是递归函数


在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。
在编程语言中，把直接或间接地调用自身的函数称为递归函数。函数的构建通常需要一个函数或者一个过程来完成。
递归函数
是建立在嵌套的基础上的，只不过嵌套调用了自己本身，而且经常不是显式调用。
一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：
1）
在每一次调用自己时，必须是（在某种意义上）更接近于解；
2）
必须有一个终止处理或计算的准则。
/////////////////////////如一个非法的递归（嵌套）调用：
void
ff(){
ff();
}
int
main()
{
ff();
system(“pause“);
return
0;
}
//////////////////////////////斐波那契数列的递归解法
/////////////////////////写法虽然简单，但是效率不高。
#include《iostream.h》
//Fibonacci
sequence
int
GetFibnRes(int
n){
if
(n》1)
{
return
GetFibnRes(n-1)
+
GetFibnRes(n-2);
}
if
(n《0)
{
cout《《“uneffective
parameter!“《《endl;
return
-1;
}
return
n;
}
int
main(){
int
n;
int
res;
while
(1)
{
cout《《“Please
input
Fibonacci
Sequence’s
number“《《endl;
cin》》n;
res=GetFibnRes(n);
cout《《res《《endl;
system(“pause“);
}
return
0;
}
-递归

递归的概念


​是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象。
在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用的对象已知。
使用递归解决问题，思路清晰，代码少。但是在主流高级语言中（如C语言、Pascal语言等）使用递归算法要耗用更多的栈空间，所以在堆栈尺寸受限制时（如嵌入式系统或者内核态编程），应避免采用。所有的递归算法都可以改写成与之等价的非递归算法。
汉诺塔问题，是常见可用递归解决的问题，不过也有非递归的解法。
菲波纳契数列可用递归定义。
以下为求汉诺塔问题的Pascal程序：
procedure Hanoi(n:integer;x,y,z:char);
递归
begin
if n《》1 then begin
Hanoi(n-1,x,z,y);
writeln(x,n,z);
Hanoi(n-1,y,x,z);
else writeln(x,n,z);
end;
end;
上述程序用接近自然语言的伪代码可表述如下：
Hanoi 过程 (整型参数n; 字符型参数 x,y,z);
//注：n 代表本步中要处理的盘子数，x,y,z 分别表示 n 号盘子原来所在柱子、经由柱子、目标柱子
开始
如果 n 不为 1 ，那么：开始
调用 Hanoi 过程 (参数为 n-1,x,z,y);
//注：这一步表示用本过程方法将剩余 n-1 个盘子从柱子 x 经由柱子 z 移动到柱子 y
输出 x,n,z; //注：表示将 n 号盘子从 x 移动到 z
调用 Hanoi 过程 (参数为 n-1,y,x,z);
//注：这一步表示用本过程方法将剩余 n-1 个盘子从柱子 y 经由柱子 x 移动到柱子 z
结束; //以上程序段就完成了把 n 个盘子从柱子 x 经由柱子 y 移动到柱子 z
否则 输出 x,n,z; //注：若 n 为1 的话本句直接输出表示将 n 号盘子从 x 移动到 z
递归，就是在运行的过程中调用自己。
构成递归需具备的条件：
函数嵌套调用过程示例
1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。
-递归

如何理解递归


递归，又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。
-递归

什么是递归函数


递归就是本身调用自己。
如n!=n(n-1)!
你定义函数f(n)=nf(n-1)
而f(n-1)又是这个定义的函数。。这就是递归。
实现递归。简单说来从未知的推到已知的
如：3!=3*2!
2!=2*1！
1！=1（已知的）
然后从已知再返回调用给上一层。到你所要求的
1!=1（已知）
2！=2*1！=2*1=2
3！=3*2！=3*2=6
递归结束
-递归

什么是递归


递归，就是在运行的过程中调用自己。构成递归需具备的条件：1. 子问题须与原始问题为同样的事，且更为简单；2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。例如，下列为某人祖先的递归定义：某人的双亲是他的祖先（基本情况）。某人祖先的双亲同样是某人的祖先（递归步骤）。斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21..... I 斐波纳契数列是典型的递归案例：递归关系就是实体自己和自己建立关系。Fib(0) = 1 [基本情况] Fib(1) = 1 [基本情况] 对所有n 》 1的整数：Fib(n) = (Fib(n-1) + Fib(n-2)) [递归定义] 尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：阶乘（1) = 1 [基本情况] 对所有n 》 1的整数：阶乘（n) = (n * 阶乘（n-1)) [递归定义] 一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这时你已经知道该怎么做的。如此的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。-递归


什么是递归程序递归程序的优缺点是什么


递归程序是指在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的程序。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。满足使用递归的条件：

  • 子问题为同类事物，且更简单

  • 必须有个出口

    • 优点：

  • 代码简洁

  • 符合思维习惯，容易理解

    • 缺点：

  • 效率较低

  • 递归层次太深，耗内存且容易栈溢出一定要使用的话，最好使用缓存避免相同的计算，限制递归调用的次数


递归是什么意思


程序调用自身的编程技巧称为递归（ recursion）。

构成递归需具备的条件有：

1、子问题须与原始问题为同样的事，且更为简单。

2、不能无限制地调用本身，须有个出口，化简为非递归状况处理。

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。-递归

扩展资料：

递归一般用于解决三类问题：

1、数据的定义是按递归定义的。（Fibonacci函数，n的阶乘）

2、问题解法按递归实现。（回溯）

3、数据的结构形式是按递归定义的。（二叉树的遍历，图的搜索）

递归的缺点：

递归解题相对常用的算法如普通循环等，运行效率较低。因此，应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，因此递归次数过多容易造成栈溢出。-递归

参考资料来源：百度百科-递归


《编程珠玑》一道练习题：二分查找的递归算法，要求函数名为int binarysearch(DataType x[], int n)


int binarysearch(DataType x,int n)
{
int low = 0;
int high = n-1,mid;
while(low《high)
{
mid = (low + high)/2;
if(x[mid]《n) low = mid+1;
else if(x[mid]》n) high = mid -1;
else
return mid;
}
return -1;
}
-递归