数据结构的递归什么意思

① 递归的重要组成

在计算机编程语言，一个递归类型（也被称为递归定义，电感定义或感应数据类型）是一种数据类型，选择那些包含相同类型的其它值的值。递归类型的数据通常被视为有向图。

递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以响应运行时要求动态增长到任意大的大小; 相反，必须在编译时设置静态数组的大小要求。

② c语言中的递归

本人学c++，c的语法已经淡忘了，但是递归不管什么语言都是一个原理
其实简单一点来说就像数学里面的数列的通项公式：
例如一个数列是2，4，6，8，10......
很容易就可以得到通项公式是a[n]=2*n n是大于0的整数
你肯定学过这个数列的另外一种表示方式就是： a[1]=2, a[n]=a[n-1]+2 n是大于1的整数
其实这就是一个递归的形式，只要你知道初始项的值，未知项和前几项之间的关系就可以知道整个数列。
程序例子：比如你要得到第x项的值
普通循环：
for(int i=1; i<=n; i++)
if (i == x)
cout << 2*i; /*cout 相当于 c里面的printf,就是输出.*/
递归：
int a(int x) {
if (x = 1)
return 2; /* 第一项那肯定是2了，这个也是递归的终止条件！ */
else return a(x-1)+2; /* 函数自身调用自身是递归的一个特色 */
比如x=4,那么用数学表示就是a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2
其实递归方法最接近自然，也是最好思考的一个方法，难点就是把对象建模成递归形式，但是好多问题本身就是以递归形式出现的。
普通递归就是数据结构上的堆栈，先进后出。
例如上面x=4,把a(4)放入栈底，然后放入a(3),然后a(2),a(1),a(1)的值已知，出栈，a(1)=2,a(2)出栈a(2)=a(1)+2=2+2=4,a(3)出栈a(3)=a(2)+2=(a(1)+2)+2=6,a(4)出栈a(4)=a(3)+2=(a(2)+2)+2=((a(1)+2)+2)+2=8
再比如楼上的阶乘例子，当n=0 或 1时,0!=1,1!=1,这个是阶乘的初始值，也是递归的终止条件。然后我们知道n!=n*(n-1)!,当n>1时,这样我们又有了递归形式，又可以以递归算法设计程序了。（楼上已给出谭老的程序，我就不写了）。
我给出一种优化的递归算法---尾递归。
从我给出的第一算法可以看出，先进栈再出栈，递归的效率是很低的。速度上完全比不上迭代（循环）。但是尾递归引入了一个新的函数参数，用这个新的函数参数来记录中间值.
普通递归阶乘fac(x),就1个x而已，尾递归用2个参数fac(x,y),y存放阶乘值。
所以谭老的程序就变成
// zysable's tail recursive algorithm of factorial.
int fac(int x, int y) {
if (x == 1)
return y;
else return fac(x-1, y*x);}
int ff(int x) {
if (x == 0)
return 1;
else return fac(x,1);}
对于这个程序我们先看函数ff，函数ff其实是对fac的一个封装函数，纯粹是为了输入方便设计的，通过调用ff(x)来调用fac(x,1),这里常数1就是当x=1的时候阶乘值了，我通过走一遍当x=3时的值即为3!来说明一下。
首先ff(3),x!=0,执行fac(3,1).第一次调用fac，x=3,y=1,x!=1,调用fac(x-1,y*x),新的x=2,y=3*1=3,这里可以看到，y已经累计了一次阶乘值了，然后x还是!=1,继续第三次调用fac(x-1,y*x),新的x=1,y=2*3=6,然后x=1了，返回y的值是6，也就是3！.你会发现这个递归更类似于迭代了。事实上我们用了y记录了普通递归时候，出栈的乘积，所以减少了出栈后的步骤，而且现在世界上很多程序员都在倡议用尾递归取消循环，因为有些在很多解释器上尾递归比迭代稍微效率一点.
基本所有普通递归的问题都可以用尾递归来解决。
一个问题以递归来解决重要的是你能抽象出问题的递归公式，只要递归公式有了，你就可以放心大胆的在程序中使用，另外一个重点就是递归的终止条件；
其实这个终止条件也是包含在递归公式里面的，就是初始值的定义。英文叫define initial value. 用普通递归的时候不要刻意让自己去人工追踪程序，查看运行过程，有些时候你会发现你越看越不明白，只要递归公式转化成程序语言正确了，结果必然是正确的。学递归的初学者总是想用追踪程序运行来让自己来了解递归，结果越弄越糊涂。
如果想很清楚的了解递归，有种计算机语言叫scheme,完全递归的语言，因为没有循环语句和赋值语句。但是国内人知道的很少，大部分知道是的lisp。
好了，就给你说到这里了，希望你能学好递归。

PS:递归不要滥用，否则程序极其无效率，要用也用尾递归。by 一名在美国的中国程序员zysable。

③ 谁给解释一下，数据结构中的递归是什么意思

递归：
递归是一种重要的编程技术。该方法用于让一个函数从其内部调用其自身。一个示例就是计算阶乘。0 的阶乘被特别地定义为 1。 更大数的阶乘是通过计算 1 * 2 * ...来求得的。

④ 在数据结构的算法中,1什么是递归,2如何设计递归算法

一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。给你一个示例做1+2+3+。。。+n
int digui(int n)
{ int t;
if(n>1)
{t=digui(n-1)+n;
return t;}
else
return 1;
}

⑤ 数据结构与算法(8)-栈与递归的关系

数据结构与算法(7)-栈

递归： 在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。 通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。

比如很多数学定义是递归的，比如阶乘、斐波那契数列，卢卡斯数列等。对于类似的复杂问题，若能拆分为几个简单的相同或类似的子问题来求解，便称为递归求解。

其数据结构本身具有递归的特性，例如链表，通过指针指向下一个节点，所以在节点中包含了自身。
示例：(打印链表内的所有元素)

在递归算法中，如果当递归结束条件成立只执行return操作时，分治法求解递归问题算法一般形式可以简化为：

有些问题虽然本身没有明显的递归结构，但是采样递归求解比迭代求解更简单，比如汉诺塔问题，皇后问题，迷宫问题

一个递归函数在其执行过程中，需要多次进行自我调用，那么递归函数是如何执行的呢？
函数调用： 在高级语言的程序中，函数的调用都是通过栈来进行的。通常在一个函数的运行期间调用另一个函数时，在运行被调用函数之前系统一般需要完成3件事情：

从被调用函数返回需要调用函数之前，系统同样需要完成3件事

当多个函数构成嵌套调用时，按照先调用后返回的原则，上述函数之间的信息传递和控制转移则需要通过栈来实现，即系统将整个程序运行时所需要的数据空间都安排在一个栈中，每当调用一个函数的时候，就在它的栈顶分配一个存储区域，每当这个函数退出时，就释放它的存储区域，从而回到调用函数栈区的栈顶。
示例：

通过汇编看函数调用栈：

一个递归函数的运行过程类似多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数，因此和每次调用相关的一个重要概念是递归函数运行的运行“层次”，假设调用该递归函数的主函数为第0层，则从主函数调用递归函数进入第1层，以后每调用一次就加一层，每返回一层就减一层，直至返回到主函数。

为了保证递归函数正确执行，系统需要设立一个“递归工作栈”作为整个递归函数运行期间使用的数据存储区，每一层递归所需信息构成一个工作记录，其中包括所有的实参，所有的局部变量，以及上一层的返回地址，每进入一层递归就产生一个新的工作记录压入栈顶，每退出一个递归就从栈顶弹出一个工作记录，则当前执行层的工作记录称为“活动记录”。

本质上讲呢，在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以递归调用的次数过多，占用内存就越多，就会导致栈溢出。

汉诺塔 ：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根 金刚石 柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

假设柱子编号分别为A、B、C，盘子的个数为n，我们要做的是将A上的所有盘子按照规则移动到C柱上，B柱作为辅助柱。计算移动次数。

⑥ C语言中的递归是什么意思

递归就是 函数自己调用自己 ..
第一个是主函数 ..
第二个cj()函数才是一个递归函数 ..
在cj()函数体里面 有cj(n--)这个语句 就是它再次调用自己 只不过参数变化了 ..

⑦ 数据结构之递归一

上一篇写了关于数学归纳法的一些概念，那么这一篇就该带大家去体会一下递归了。

这一篇主要通过一个小游戏带领大家走入递归的世界，这个游戏叫做 汉诺塔 ，先说下游戏规则，如下图所示，有三根柱子，我们需要把套在 A 柱子上的圆环全部移动到 B 上，一次只能移动一个圆环，当然圆环的顺序也得一样。那么 C 柱则起到了中转的作用。

下面是最终需要达到的结果

有点人可能会说，一开始就让我们接触这么多的圆环，怎么也会搞混啊，那么我们就先从简单一点的开始吧。先从只有三个的圆环入手。

这里我们需要把 A 上的三个圆环借助 C 全部移动到 B 柱上。首先开始之前我们应该思考下，要想把三个全部移动到 B 柱上，则先需要把上面两个拿到 C 柱，然后把最大的那个拿到 B 柱，最后把上面的两个放到最大的上面。当我们把两个环拿到 C 的时候，势必需要借助 B 柱作为一个临时中转，这样我们就完成了移动的过程。写成规范一点的步骤就是：

步骤一： 把两个环从 A 柱经过 B 柱进行中转移动到 C 柱。

步骤二： 把第三个环拿到 B 柱。

步骤三： 把两个环从 C 柱经过 A 柱进行中转移动到 B 柱。

经过这三个步骤我们就实现了三个圆环的移动。这时候我们就可以结合上一篇讲过的数学归纳法进行递推到如果有 n 个圆环怎么移动的问题了。

首先，如果 n = 0 ，不做任何移动。

其次，如果 n > 0 ，做三个步骤：

步骤一： 把 n - 1 个环从 A 柱经过 B 柱进行中转移动到 C 柱。

步骤二： 把第 n 个环拿到 B 柱。

步骤三： 把 n - 1 个环从 C 柱经过 A 柱进行中转移动到 B 柱。

至于如何把 n - 1 个圆环移动，上面通过两个环的例子已经给大家进行了简单的说明，这就是递归和数学归纳法的不同之处了，数学归纳法是先知道简单的怎么做去推导出一般的结论，而递归则是知道一般的要求，通过把一般的问题化成简单的问题来解决。如果大家光听理论有些混乱的话，可以去玩玩汉诺塔的小游戏体会下

当然最后我们得从程序员的角度去实现一下汉诺塔的解法

我们可以通过游戏对程序的结果进行验证，在下一篇中会对这个游戏有个简短的总结。

这一篇通过一个小游戏带大家粗略了解了递归的概念，后面还将有两个例子和一个总结对递归进行了解。

⑧ 数据结构中的二叉树中的递归怎么理解

数据结构中的二叉树中的递归理解如下：

具体实现代码

1 function preorder(node){

2 if(!!node){//转换为布尔值

3 divlist.push(node);

4 preorder(node.firstElementChild);

5 preorder(node.lastElementChild);

6 }

7 }

对代码的几点说明：

divlist为一个数组，是一个全局变量，存储最终遍历结果。可能有的同学不熟悉JavaScript，node.firstElementChild与node.lastElementChild分别指父节点的第一个元素节点和最后一个元素节点，即对应父节点的左孩子和右孩子。

二叉树是以DOM树的形式模拟

所谓递归可以分为两部分来理解：“递”和“归”。

“递”指按照代码执行顺序执行，这个和我们正常的思维一致不难理解。但有一点需要注意的是，在“递”的同时会把节点按照访问的顺序逐次压入到一个堆栈中。

“归”是指“递”进行到尽头时，开始根据“递”的过程中形成的堆栈进行出栈，最终得到结果。

对于二叉树的先序遍历，可以看出包含了两个对自己的调用，及包含两个遍历。

我们首先传进去的node是1，根据程序执行过程，我们可以知道在执行到一个阶段的尽头时，将会形成这样一个堆栈

由于左子树已经到了尽头，所以第一个遍历暂告一段落。按照代码执行的顺序，接下来需要执行preorder(node.lastElementChild);也就是右子树的遍历，因为4依然没有右孩子，所以按照出栈的顺序依次遍历2和1的右子树。为了说明简单，再次贴一下代码

1 function preorder(node){

2 if(!!node){//转换为布尔值

3 divlist.push(node);

4 preorder(node.firstElementChild);

5 preorder(node.lastElementChild);

6 }

7 }

再来具体分析一下遍历2的右孩子时的过程。

当把2的节点传给preorder函数时，只执行了preorder(node.firstElementChild);，preorder(node.lastElementChild);还没有执行，按照程序执行顺序此时需要执行。

具体的执行步骤如下：

此时堆栈内又依次被压入了5，6，7三个元素节点

总结

递归也没有那么可怕，该执行的代码还是会执行，不过顺序可能和我们平常的思维不一致。它会不断的调用自身直到一个停止条件的满足，然后再回溯会第一个节点。

⑨ 递归方法的定义

1、定义是递归的：

（1）n!的递归实现：

递归方法：

public class Method { int fun(int n){ if(n==1) return 1; else
return(fun(n-1)*n);
}
}
public class RecursionDemo { public static void main (String[] args){
Method m=new Method(); int num=m.fun(3);
System.out.println(num);
}
}

递归方法分析：

（1）该方法是直接递归，即自己调用自己。

例如：在执行fun(3)的时候，先执行fun（2）*3，而fun（2）=fun（1）*2，fun（1）=1。

（2）递归过程将问题的规模逐步缩小，参数的大小每次减1。一个个重复的过程，通过调用自身，减少了代码量。

（3）因为递归调用语句是在最后一句，因此，这种递归方式也称为尾递归。

2、数据结构是递归的：

单链表的存储结构定义。

3、问题的求解是递归的：

#include<stdio.h> #include<malloc.h> #include<stdlib.h>#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10#define OVERFLOW -2#define ERROR 0
#define OK 1typedef int ElemType;

typedef struct{ //存储结构 ElemType *elem; //指针类型 int length;
int listsize;
}SqList;//顺序表的结构类型 typedef int Status;

Status InitList(SqList &L){
L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//动态分配存储空间 if(!L.elem) exit(OVERFLOW); //分配失败退出 L.length=0; //空表 L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK;
}

Status ListInsert(SqList &L,int i,ElemType e){//在第 i 个元素前插入一个新的元素e if(i<1 || i > L.length+1) return ERROR; //i值不合法 if(L.length>=L.listsize) //存储空间不足 {
ElemType * newbase=(ElemType *)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) exit(OVERFLOW); //分配失败 L.elem=newbase;
L.listsize=LIST_INIT_SIZE+LISTINCREMENT;
}
for (int j=L.length; j>=i; --j)
L.elem[j]=L.elem[j-1];
L.elem[i-1]=e;
L.length++;return OK;
}

Status ListEmpty(SqList L){ //判断顺序表是否为空return L.length == 0;
}

Status ListPrint(SqList &L) {
printf(" 顺序表为： ");
if (ListEmpty(L)) {
printf(" 空。 ");
return ERROR;
}
for (int i=0; i<L.length; ++i)
{
printf("%-4d ", L.elem[i]);
}
printf(" ");
return OK;
}int Sum(SqList L,int i){ if(i==L.length) return 0; else
return(L.elem[i]+Sum(L,i+1));
}

main(){

SqList L;
ElemType e;
int i,j;
InitList(L);


printf(" 请输入你想创建的顺序表中元素的个数： ");
scanf("%d",&i);
if(i<1) printf(" 您输入的值有误，无法创建顺序表。 ");
else {
printf(" 请您依次输入您想创建的顺序表的元素： ");
for(j=1;j<=i;j++)
{
scanf("%d",&e);
ListInsert(L,L.length+1,e); //尾插 }
}
ListPrint(L); //遍历顺序表 int result=Sum(L,0);
printf( "顺序表所有元素的和为：%d",result);
}

这个程序是求解顺序表的元素的和，从顺序表的第一个元素开始，依次向后查找元素，并进行求和运算。

⑩ 数据结构中的二叉树中的递归怎么理解

//递归方法实现创建
status createbitree(bitree *t)
{
int ch=0;
cin>>ch;
if(ch==0)(*t)=NULL;
else
{
(*t)=(bitree)malloc(sizeof(binode));
(*t)->data=ch;
createbitree(&(*t)->lchild);
createbitree(&(*t)->rchild);
}
return OK;
}
这是个按条件先序遍历的顺序输入的二叉树，你必须理解的是这些代码中的递归有一个隐含的条件就是利用栈来进行存储，有一个压栈和出栈的过程，栈起了一个保护现场的作用，左孩子是优先的，一直到这个结点为空，才进行弹栈将这个结点的父亲结点，并且进入这个父亲结点的右孩子，对这个过程重复。
有什么问题可以继续找我，数据结构我学的还可以的