递归算法c语言（C语言二叉树递归算法怎么做）

本文目录

• C语言二叉树递归算法怎么做
• C语言递归算法的原理是什么
• C语言什么是递归方法
• c语言递归算法
• C语言递归算法是怎么执行的
• C语言递归问题！
• C语言递归算法

C语言二叉树递归算法怎么做

#include 《stdio.h》#include 《string.h》struct treenode{    int value;    treenode* left;    treenode* right;};typedef treenode* BiTree;void visit(treenode* node){    printf(“%2d “, node-》value);}//    结点总数 int node(BiTree T){    if( !T ){        return 0;    }    return node(T-》left) + node(T-》right) + 1;}//    前序 void preOrder(BiTree T){    if( T ){        visit(T);        preOrder(T-》left);        preOrder(T-》right);        }}//    中序void inOrder(BiTree T){    if( T ){        inOrder(T-》left);        visit(T);        inOrder(T-》right);        }    } //    后序void postOrder(BiTree T){    if( T ){        postOrder(T-》left);        postOrder(T-》right);            visit(T);    }    } //    叶子节点数int leafnode(BiTree T){    if( T ){        if( !T-》left && !T-》right )            return 1;        else            leafnode(T-》left) + leafnode(T-》right);        }else{        return 0;    }} int height(BiTree T){    if( T ){        int lh = height(T-》left);        int rh = height(T-》right);        return (lh》rh ? lh:rh) + 1;    }else{        return 0;    }}int main(){        return 0;}

C语言递归算法的原理是什么

调用自身，完成重复性工作。也就是在函数或子过程的内部，直接或者间接地调用自己的算法。如：3! = 2! * 3 2! = 1! * 2 1! = 1所以;s(n){if (n == 1 || n == 0)return (1);else return (n * s(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 (a》b)?(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 (left《right)? (right +1) : (left + 1);     else return -1; }

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

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

c语言递归算法

用递归法计算n!用递归法计算n!可用下述公式表示： n!=1 (n=0,1) n×(n-1)! (n》1)按公式可编程如下：long ff(int n){ long f; if(n《0) printf(“n《0,input error“); else if(n==0||n==1) f=1; else f=ff(n-1)*n; return(f);}main(){ int n; long y; printf(“\ninput a inteager number:\n“); scanf(“%d“,&n); y=ff(n); printf(“%d!=%ld“,n,y);} 程序中给出的函数ff是一个递归函数。主函数调用ff 后即进入函数ff执行，如果n《0,n==0或n=1时都将结束函数的执行，否则就递归调用ff函数自身。由于每次递归调用的实参为n-1，即把n-1的值赋予形参n，最后当n-1的值为1时再作递归调用，形参n的值也为1，将使递归终止。然后可逐层退回。下面我们再举例说明该过程。设执行本程序时输入为5，即求5!。在主函数中的调用语句即为y=ff(5)，进入ff函数后，由于n=5,不等于0或1，故应执行f=ff(n-1)*n,即f=ff(5-1)*5。该语句对ff作递归调用即ff(4)。进行四次递归调用后，ff函数形参取得的值变为1，故不再继续递归调用而开始逐层返回主调函数。ff(1)的函数返回值为1，ff(2)的返回值为1*2=2，ff(3)的返回值为2*3=6，ff(4)的返回值为6*4=24，最后返回值ff(5)为24*5=120。

C语言递归算法是怎么执行的

递归就是自己调用自己，例如你写的 net（）函数，函数自己调用自己。它调用自己的时候，不管程序运行到了哪，见到自己直接跳转，进入到下一个自己中运行，直到不满足跳入下一个自己的条件时，运行完当前函数，然后回到前一个自己中，回到跳出位置，继续运行没有完事的部分，直到完成当前函数，然后回到上一个自己。。。。这样直到回到第一个自己，运行开始跳出时没有完成部分的程序。这就是递归；

C语言递归问题！

　递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。　　递归算法的特点　　递归过程一般通过函数或子过程来实现。　　递归算法：在函数或子过程的内部，直接或者间接地调用自己的算法。　　递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。　　递归算法解决问题的特点：　　(1) 递归就是在过程或函数里调用自身。　　(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。　　(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。　　(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。　　递归算法所体现的“重复”一般有三个要求：　　一是每次调用在规模上都有所缩小(通常是减半)；　　二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；　　三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。　例子如下：　　描述：把一个整数按n(2《=n《=20)进制表示出来，并保存在给定字符串中。比如121用二进制表示得到结果为：“1111001”。　　参数说明：s: 保存转换后得到的结果。　　n: 待转换的整数。　　b: n进制（2《=n《=20）　　void　　numbconv(char *s, int n, int b)　　{　　int len;　　if(n == 0) {　　strcpy(s, ““);　　return;　　}　　/* figure out first n-1 digits */　　numbconv(s, n/b, b);　　/* add last digit */　　len = strlen(s);　　s[len] = “0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ“[n%b];　　s[len+1] = ’\0’;　　}　　void　　main(void)　　{　　char s;　　int i, base;　　FILE *fin, *fout;　　fin = fopen(“palsquare.in“, “r“);　　fout = fopen(“palsquare.out“, “w“);　　assert(fin != NULL && fout != NULL);　　fscanf(fin, “%d“, &base);　　/*PLS set START and END*/　　for(i=START; i 《= END; i++) {　　numbconv(s, i*i, base);　　fprintf(fout, “%s\n“, s);　　}　　exit(0);　　}

C语言递归算法

本人学c++，c的语法已经淡忘了，但是递归不管什么语言都是一个原理其实简单一点来说就像数学里面的数列的通项公式：例如一个数列是2，4，6，8，10......很容易就可以得到通项公式是a[n]=2*n n是大于0的整数你肯定学过这个数列的另外一种表示方式就是： a=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。

递归