精华内容
下载资源
问答
  • 递归调用学习笔记

    2016-08-27 21:25:11
    所谓函数的递归调用是指在调用一个函数的过程中出现直接或间接调用该函数自身的情况。例如,在调用f1()函数的过程中,又调用了f1()函数,这称为直接递归调用;而在调用f1()函数的过程中,调用了f2()函数,又在调用了...

            所谓函数的递归调用是指在调用一个函数的过程中出现直接或间接调用该函数自身的情况。例如,在调用f1()函数的过程中,又调用了f1()函数,这称为直接递归调用;而在调用f1()函数的过程中,调用了f2()函数,又在调用了f2()函数的过程中调用了f1()函数,这称为间接递归调用。

           提到递归调用,最常用的例子就是求一个正整数的阶乘问题。例如,求整数5的阶乘,即5!。由于5!=5*4!,4!=4*3!,… 1!=1*0!,而0!等于1是已知的。于是可求出5!=5*4*3*2*1*1等于120。

    由此可见,使用递归调用解决问题的方法如下:

    原有的问题能够分解为一个新的问题,而新的问题有用到了原有问题的解法,这就出现了递归。按这一原则分解下去,每次出现的新问题是原问题简化后的子问题,最终分解出来的新问题是一个已知解的问题。这便是递归调用。

    一、递归调用的过程

    递归调用可分为两个阶段:

    1. “递推”阶段:将原问题不断分解为新的子问题,逐渐从未知向已知的方向推测,最终到达已知的条件,即递归结束条件,这是递推阶段结束。
    2. “回归”阶段:该阶段是从已知的条件出发,按照“递推”的逆过程,逐一求值回归,最后到达递推的开始处,结束回归阶段,完成递归调用。

    二、递归调用的特点

    (1)  递归调用方法编写程序简洁清晰,可读性强;

    (2)  递归调用在时间和空间的开销上比较大,既要花费较长的计算时间,又要占用较多的内存单元。

    三、递归调用实例

    (1)   求阶乘

    (2)   求前n项的和

    (3)   Fibonacci函数

    (4)  汉诺塔问题

    (5)  二叉树遍历

    (6)  二叉树的所有路径

                 ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------

                 1.求阶乘代码:

    #include"iostream"
    using namespace std;
    
    long int fac(int n);
    int main(){
      int n;
      cout<<"Input a positive integer:"<<endl;
      cin>>n;
      long fa=fac(n);
      cout<<n<<"!="<<fa<<endl;
       system("pause");
       return 0;
    }
    
    long int fac(int n){
    	 long int p;
    	 if(n==0) p=1;
    	 else p=n*fac(n-1);
    	 return p;
    }
    (2)求前n项的和代码(1+2+3+4+5+6....)
    #include"iostream"
    using namespace std;
    
    class Recursion {  
    public:
    	Recursion(int x,int y):sum(x),a(y){}
    	void add(){  
    	   sum+=a; a++;  
    	   if(a<=5) {  
    		add();//调用自身实现递归  
    	   } 
    	}
    public:
    	int sum;  
    	int a; 
    };  
    
    int main() {  
         Recursion T(0,1);
    
    	 T.add();
    	 cout<<"sum="<<T.sum<<endl;
    	 system("pause");
    	 return 0;
    }  

    (3)   Fibonacci函数(斐波那契数列)

    斐波那契数列是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

    第1项是0,第2项是第一个1,这个数列从第3项开始,每一项都等于前两项之和。

            Fibonacci函数的数学表达式为:

     
                                                           
             Fibonacci函数代码:

    #include"iostream"
    using namespace std;
     
    long int Fib(int n){
    	if(n==1) return 0;
    	else if(n==2)return 1;
    	else return Fib(n-1)+ Fib(n-2);
    }
    
    int main() { 
    	int n;
        cout<<"Input a positive integer:";
        cin>>n;
        long int f=Fib( n);
    	cout<<"Fib("<< n<<")="<<f<<endl;
    	system("pause");
    	return 0;
    } 

    (4)  汉诺塔问题

    有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:

    (1)每次只能移动一个圆盘;

    (2)大盘不能叠在小盘上面。

    注:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须遵循上述两条规则。


          汉诺塔问题代码
    #include <iostream>
    #include <cstdio>
    using namespace std;
    int T=0; //移动的次数
    void hannoi (int n, char from, char buffer, char to){
        if (n == 1){
            cout << "Move disk " << n << " from " << from << " to " << to << endl;
    	    T++;
    	}
        else{
            hannoi (n-1, from, to, buffer);
            cout << "Move disk " << n << " from " << from << " to " << to << endl;
    		T++;
            hannoi (n-1, buffer, from, to);
        }
    }
     
    int main()
    {
        int n;
    	cout<<"输入圆盘的个数:";
        cin >> n;
        hannoi (n, 'A', 'B', 'C');
    	cout<<"移动的次数:"<<T<<endl;
    	system("pause");
        return 0;
    } 

    (5)  二叉树遍历

    二叉树有3个基本组成单元:根节点(D)、左子书(L)、右子树(R)。二叉树的遍历分为三种:前(先)序、中序、后序遍历。则先(根)序遍历二叉树的顺序是DLR,中(根)序遍历二叉树的顺序是LDR,后(根)序遍历二叉树的顺序是LRD。还有按层遍历二叉树。这些方法的时间复杂度都是O(n),n为结点个数。

             递归调用遍历二叉树代码:

    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    struct node{
        int data;          //数据元素
        node *left,*right; //指向左子树、右子树
    };
    class Btree
    {
       static int n;
       static int m;
    public:
        node *root;
        Btree(){
            root=NULL;
        }
        void create_Btree(int);                 //构造二叉树
        void Preorder(node *);                  //先序遍历
        void inorder(node *);                   //中序遍历
        void Postorder(node *);                 //后序遍历
        void display1() {Preorder(root); cout<<endl;}
        void display2() {inorder(root);cout<<endl;}
        void display3() {Postorder(root); cout<<endl;}  
    };  
    
    int Btree::n=0;
    int Btree::m=0;
    void Btree::create_Btree(int x){
        node *newnode=new node;   //新建一个节点
        newnode->data=x;          //节点赋值  
        newnode->right=newnode->left=NULL;//并且新节点的左右子树为空
        if(root==NULL)     //根节点是否为空
            root=newnode;  //根节点是否为空时,根节点为newnode
        else{
            node *back;
            node *current=root; 
    		//将大于根节点的值赋给右子树,小于根节点的数赋给左子树
            while(current!=NULL){
                back=current;
                if(current->data>x) 
                    current=current->left;
                else
                    current=current->right;
            }
            if(back->data>x)
                back->left=newnode;
            else
                back->right=newnode;
        }
    }
    void Btree::Preorder(node *temp)    //这是先序遍历二叉树,采用了递归的方法。
    {
        if(temp!=NULL){
            cout<<temp->data<<" ";
            Preorder(temp->left);
            Preorder(temp->right);
        }
    }
    void Btree::inorder(node *temp)      //这是中序遍历二叉树,采用了递归的方法。
    {
        if(temp!=NULL){
            inorder(temp->left);
            cout<<temp->data<<" ";
            inorder(temp->right);
        }
    }
    void Btree::Postorder(node *temp)     //这是后序遍历二叉树,采用了递归的方法。
    {
        if(temp!=NULL){
            Postorder(temp->left);
            Postorder(temp->right);
            cout<<temp->data<<" ";
        }
    }
    
    void main()
    {
        Btree A;
        int array[]={7,4,2,3,15,35,6,45,55,20,1,14,56,57,58};
        int k;
        k=sizeof(array)/sizeof(array[0]); //数组元素个数
        cout<<"建立排序二叉树顺序: "<<endl;
        for(int i=0;i<k;i++){
            cout<<array[i]<<" ";
            A.create_Btree(array[i]);
        }
        cout<<endl;
        cout<<endl<<"先序遍历序列: "<<endl;
        A.display1();
        cout<<endl<<"中序遍历序列: "<<endl;
        A.display2();
        cout<<endl<<"后序遍历序列: "<<endl;
        A.display3();
    	system("pause");
    }
    程序中构造的二叉树如下图所示


    (6)  二叉树的所有路径

    当一个节点的左右子树都为空时,把从根节点到该节点的路径保存在向量中,找到所有的叶子节点就完成了对所有路径的保存.

    二叉树所有路径代码:

    #include <iostream>  
    #include <cstdio>  
    #include <stdio.h>
    #include <vector> 
    #include <string> 
    
    using namespace std;
    
    struct node {
    	int data;          //数据元素  
    	node *left, *right; //指向左子树、右子树
    	node() {}
    	node(int val) {
    		this->data = val;
    		this->left = this->right = NULL;
    	}
    };
    
    class Btree
    {
    public:
    	node *root;
    	Btree() {
    		root = NULL;
    	}
    	void create_Btree(int);                 //构造二叉树  
    };
    
    class PathsBtree {
    public:
    	/**
    	* @param root the root of the binary tree
    	* @return all root-to-leaf paths
    	*/
    	vector<string> binaryTreePaths(node* root) {
    		vector<string>Paths;
    		if (root == NULL) return Paths;
    		bTreePathsCore(root, Paths, to_string(root->data));
    		return Paths;
    	}
    	void bTreePathsCore(node *root, vector<string>&Paths, string strPaths)
    	{
    		if (root->left == NULL&&root->right == NULL) {
    			Paths.push_back(strPaths);
    			return;
    		}
    		if (root->left != NULL)
    			bTreePathsCore(root->left, Paths, strPaths + "->" + to_string(root->left->data));
    		if (root->right != NULL)
    			bTreePathsCore(root->right, Paths, strPaths + "->" + to_string(root->right->data));
    	}
    };
    
    
    void Btree::create_Btree(int x) {
    	node *newnode = new node;   //新建一个节点  
    	newnode->data = x;          //节点赋值    
    	newnode->right = newnode->left = NULL;//并且新节点的左右子树为空  
    	if (root == NULL)     //根节点是否为空  
    		root = newnode;   //根节点是否为空时,根节点为newnode  
    	else
    	{
    		node *back=NULL;
    		node *current = root;
    		//将大于根节点的值赋给右子树,小于根节点的数赋给左子树  
    		while (current != NULL) 
    		{
    			back = current;
    			if (current->data>x)
    				current = current->left;
    			else
    				current = current->right;
    		}
    		if (back->data>x)
    			back->left = newnode;
    		else
    			back->right = newnode;
    	}
    }
    
    void main()
    {
    	Btree A;
    
    	int array[] = { 7,4,2,3,15,35,6,45,55,20,1,14,56,57,58 };
    	int k;
    	k = sizeof(array) / sizeof(array[0]); //数组元素个数  
    
    	cout << "建立排序二叉树顺序: " << endl;
    	for (int i = 0; i<k; i++) {
    		cout << array[i] << " ";
    		A.create_Btree(array[i]);
    	}
    
    	PathsBtree pa;
    	vector<string> path=pa.binaryTreePaths(A.root);
    
    	for (int i = 0; i < path.size();i++) {
    		cout <<"root-to-leaf path "<<(i+1)<<":"<< path.at(i) << endl;
    	}
    
    	system("pause");
    }
    


    参考资料:http://www.cnblogs.com/elleniou/archive/2012/05/03/2480042.html

                   http://www.cricode.com/3489.html

                  http://blog.csdn.net/fanglegefang/article/details/70477509


    展开全文
  • 递归调用

    2010-11-27 10:57:00
    所谓递归-recursive就是可以在方法里自己调用自己。以下是一个最简单的递归(当然会是死循环,所以真正的递归不要这样写) public void sayHi(){ System.out.println(“Hello!”); sayHi(); //自己调用自己,会无数...

    所谓递归-recursive就是可以在方法里自己调用自己。

    以下是一个最简单的递归(当然会是死循环,所以真正的递归不要这样写)

                      public void sayHi(){
                           System.out.println(“Hello!”);
                            sayHi(); //自己调用自己,会无数次的调用
    }
    以上的这个程序如果你运行的话,最终会StackOverFlow也就是堆栈溢出错误

       真正的递归应用之一:求某个数的阶乘 
                      public int fact(int n){
                  
                    if(n>0)
                       return n*fact(n-1);
               else
                     return 1;
    }

     

    假如参数是4它的调用顺序如下图1所示:


    递归调用 
                     图1-递归调用示意图

     

    int strlen(char *p)  // 注意! 不允许定义任何变量
    {
      if( *p )
      return strlen(p + 1)+ 1;
      return 0;
    }
    int strlen(char* p, int add_num=0)
     {
        return '/0'==*p?add_num:strlen(p+1, add_num+1);
     }
    用strlen()计算字符串的长度不包括'/0'
    已知 char *str1="absde";
         char str2[]="absde";
         char str3[8]={'a',};
         char ss[] = "0123456789";
    sizeof(str1)=4;
     sizeof(str2)=6;
          sizeof(str3)=8;
           sizeof(ss)=11
    总之,对于指针,sizeof操作符返回这个指针占的空间,一般是4个字节;而对于一个数组,sizeof返回这个数组所有元素占的总空间。char*与char[]容易混淆,一定要分清,而且而strlen不区分是数组还是指针,就读到/0为止返回长度。而且strlen是不把/0计入字符串的长度的。
     char a[]="abc/0efg";
        printf("%d",strlen(a));  ///3  遇 '/0'结束
     printf("%d",sizeof(a));     ///8  只是一个操作符
    strlen和sizeof的区别:
    sizeof在编译器求解,strlen在运行期求解,这是主要区别
    其次strlen只能求C风格字符串长度sizeof()可以求很多类型的大小
    是否计算'/0'
    展开全文
  • 递归调用图例

    2016-02-02 20:26:00
    结合例题对该问题的分析,根据左边给出的输入数据完成下列递归调用示意图的填空部分. ————————————答案———————————————— ———————————————————...

    根据这一简单的事例,可以帮助初学者理解递归。

    例6.28  已知一个一维数组A[1..N](N<50),又已知一整数M。 如能使数组A中任意几个元素之和等于M,则输出YES,反之则为NO。

    结合例题对该问题的分析,根据左边给出的输入数据完成下列递归调用示意图的填空部分.

     

    ————————————答案————————————————

    ——————————————————————————————————————————

    ——————————————————答案——————————————————————

     

    转载于:https://www.cnblogs.com/vacation/p/5178447.html

    展开全文
  • 使用递归调用的代码可读性高,易于理解。就拿斐波那契数列为列,在初学编程时应该都使用过递归求斐波那契数列吧。递归的实例还有很多,如我们的汉诺塔问题,构建二叉树等等。相信现在让大家用递归写一个递归求阶乘...

    递归函数:一个含直接或间接调用本函数语句的函数被称之为递归函数。

    在很多的编程实例中都会用到递归的方式解决问题,在许多问题上使用递归的思想解题也会非常方便。使用递归调用的代码可读性高,易于理解。就拿斐波那契数列为列,在初学编程时应该都使用过递归求斐波那契数列吧。递归的实例还有很多,如我们的汉诺塔问题,构建二叉树等等。相信现在让大家用递归写一个递归求阶乘什么的都分分钟可以解决,递归嘛,简单的很。可是…你真的有了解过递归吗?

    今天我们的主题是,递归调用的几种传值方式,以及几个简单的递归调用图分析。

    下面进入正题。

    1. 函数形参的几种传值方式比较

    在我们C/C++语言中,有几种特殊的传值方式。例如一个 int fun(int n) 的函数,我们就有以下几种常用的传值方式。定义:int n = 10;

    • fun(n);普通的实参传形参。
      fun(n) ==》 fun(10)
    • fun(n-1); 或 fun(n+1); 一般用于递归函数中,缩小计算规模。
      fun(n+1) ==》 fun(11)
    • fun(n–); 或 fun(n++);是 fun(n);n++;的简写。
      fun(n++) ==》 fun(10)
    • fun(–n); 或 fun(++n);是 n=n+1;fun(n);的简写。
      fun(++n) ==》fun(11)

    此外,还有一种特殊的传值方式,那就是C++中的引用传递。int fun(int& n)int n = 10

    • fun(n) ==》fun(10)

    这几种传值方式,在一般的函数中都基本不会出现什么问题。但是,如果把他们用在了递归函数中那可就不一样了。

    2. 参考以下代码,请认真思考其调用过程,并画出他们的递归调用图。

    示范:如斐波那契数列递归式

    int Fib(int n)
    {
    	if (n <= 2)	return 1;
    	else return Fib(n - 1) + Fib(n-2);
    }
    
    int main() { Fib(5); return 0; }
    

    其五次的递归调用图为:

    1递归
    1递归
    2递归
    2递归
    2递归
    2递归
    3递归
    3递归
    1
    2
    3
    4
    5
    .3
    2.
    .2
    .1

    请参考示范完成下列各示例。

    2.1 示例:使用 fun(i+1) 递归调用

    参考代码:

    void fun1(int i, int n)
    {
    	if (i >= n)
    	{
    	}
    	else
    	{
    		fun1(i + 1, n);
    		fun1(i + 1, n);
    	}
    
    }
    
    int main()
    {
    	fun1(0,3);
    	return 0;
    }
    

    请认真思考其调用过程,并画出他们的递归调用图。





    2.2 示例:使用 fun(++i) 递归调用

    参考代码:

    void fun2(int i, int n)
    {
    	if (i >= n)
    	{
    	}
    	else
    	{
    		fun2(++i, n);
    		fun2(++i, n);
    	}
    
    }
    
    int main()
    {
    	fun2(0,3);
    	return 0;
    }
    

    请认真思考其调用过程,并画出他们的递归调用图。





    2.3 示例:使用 fun(++i)的引用传递的递归调用

    参考代码:

    void fun3(int &i, int n)
    {
    	if (i >= n)
    	{
    	}
    	else
    	{
    		fun3(++i, n);
    		fun3(++i, n);
    	}
    
    }
    
    int main()
    {
    	int a = 0;
    	fun3(a,3);
    	return 0;
    }
    

    请认真思考其调用过程,并画出他们的递归调用图。





    2.4 示例:使用 fun(i++) 的递归调用

    参考代码:

    void fun4(int i, int n)
    {	
    	if (i >= n)
    	{
    	}
    	else
    	{
    		fun4(i++, n);
    		fun4(i++, n);
    	}
    
    }
    
    int main()
    {
    	fun4(0,3);
    	return 0;
    }
    

    请认真思考其调用过程,并画出他们的递归调用图。





    3. 答案:调用过程分析

    通过分析递归结构我们可以知道该段代码在运行时的调用可以看做是一个二叉树。

    这里我们在每次递归调用时,打印 i 的值,分析调用过程。这里输出的 i 的序列是对其进行前序二叉遍历的结果。

    3.1 示例递归调用图解:使用 fun(i+1) 递归调用
    void fun1(int i, int n)
    {
    	cout << i << " " ;
    	if (i >= n)
    	{
    	}
    	else
    	{
    		fun1(i + 1, n);
    		fun1(i + 1, n);
    	}
    
    }
    
    // 输出:0 1 2 3 3 2 3 3 1 2 3 3 2 3 3
    
    //       以下用每层调用时i的值,分析递归调用过程         
    //			        0
    //				/	    \
    //			   1	     1
    //			 /  \       / \
    //          2   2      2   2
    //		   /\   /\    /\   /\
    //	      3  3  3 3  3 3   3 3
    
    3.2 示例递归调用图解:使用 fun(++i) 递归调用
    void fun2(int i, int n)
    {
    	cout << i << " " ;
    	if (i >= n)
    	{
    	}
    	else
    	{
    		fun2(++i, n);
    		fun2(++i, n);
    	}
    
    }
    
    // 输出:0 1 2 3 4 3 2 3 4
    
    //       以下用每层调用时i的值,分析递归调用过程    
    //			      0
    //				/   \
    //			   1	 2
    //			 /  \   / \
    //          2    3 3   4
    //		   /\      
    //	      3  4   
    
    3.3 示例递归调用图解:使用 fun(++i)的引用传递的递归调用
    void fun3(int &i, int n)
    {
    	cout << i << " " ;
    	if (i >= n)
    	{
    	}
    	else
    	{
    		fun3(++i, n);
    		fun3(++i, n);
    	}
    
    }
    
    // 输出:0 1 2 3 4 5 6
    
    //       以下用每层调用时i的值,分析递归调用过程  
    //			      0
    //				/   \
    //			   1	 6
    //			 /  \  
    //          2    5 
    //		   /\      
    //	      3  4
    
    3.4 示例递归调用图解:使用 fun(i++) 的递归调用
    void fun4(int i, int n)
    {
    	cout << i << " ";
    	if (i >= n)
    	{
    	}
    	else
    	{
    		fun4(i++, n);
    		fun4(i++, n);
    	}
    
    }
    
    // 输出:0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... ...
    
    //       以下用每层调用时i的值,分析递归调用过程 
    //				0
    //			   /
    //		      0
    //			 /
    //		    0
    //		   /
    //		  0
    //		 /
    //		0
    //	  ...
    
    
    分析:引用传递 和 i++ 传递对程序造成的影响

    这里主要对引用传递i++ 传递进行分析。

    • void fun3(int &i, int n) 引用传递的参数与原参数实际上是一个变量。可以认为引用传递的参数对整个函数是全局作用域的,在函数内参数改变时,将会对整个函数产生影响。
    递归过程
    传值
    修改
    传值
    修改
    传值
    修改
    传值
    修改
    递归函数第一次调用
    引用& n
    递归函数第二次调用
    递归函数第三次调用
    递归函数第n次调用
    • fun4(i++) ,这种传值方式等同于为 fun4(n) 。这就形成了死递归,而递归函数严格意义上来说并没有无限递归、死递归的说法。因为,递归调用时在栈上开辟空间,而栈的大小是有限制的,当我们程序说使用的栈空间超过了栈的容量时就会发生栈溢出错误。我这里使用的 vs 编译器,经测试栈空间大小约为 1M左右,在 Centos 7 下测试栈空间约为 8M 左右。
    4. 输出调用过程,打印树形结构

    既然我们已经分析出了他的调用过程,不妨再设计程序打印出其调用过程的树形结构图。

    4.1 设计程序打印以上三种递归的递归过程

    首先,定义一个结点,保存树的结点深度和结点值

    struct node		// 保存树的结点
    {
    	node(int _dep, int _val) :dep(_dep), val(_val)
    	{}
    	int dep;		// 根节点的深度
    	int val;		// 根节点的数值
    };
    

    其次,定义“打印树”类,主要数据成员有 left和right ,分别保存树的左右子树结点。以及增加左右子树的方法和一个输出树结构的方法。

    class PrintTree
    {
    public:
    	void addLeft(node tmp)
    	{
    		left.push_back(tmp);
    	}
    	void addRight(node tmp)
    	{
    		right.push_back(tmp);
    	}
    
    	void showTree(int depth);
    private:
    	vector<node> left;
    	vector<node> right;
    };
    

    实现输出树结构层次的方法,这里要借助一个“数的深度”参数来实现,打印相同深度的结点。另外,为了让输出的“树形”更直观,我们再根据树的深度不同打印数量不同的空格。

    void PrintTree::showTree(int depth)
    {
    	cout << "\t0" << endl;		// 根节点
    	
    	int i = 1;
    	while (i <= depth)
    	{
    		vector<node>::const_iterator lt = left.begin();
    		vector<node>::const_iterator rt = right.begin();
    		
    		int sp = depth - i;				/* 打印空格 */
    		while (sp-- ){	cout << "   ";}
    
    		while (lt<left.end())	
    		{
    			if ((*lt).dep == i)		/* 输出深度为 i 的左结点 */
    			{
    				cout << (*lt).val ;
    				int s = depth - i+1;		/* 打印空格 */
    				while (s--) { cout << " "; }
    			}
    			
    			lt++;
    		}
    		while (rt < right.end())	/* 输出深度为 i 的右结点 */
    		{
    			if ((*rt).dep == i)
    			{
    				cout << (*rt).val ;
    				int s = depth - i +1;		/* 打印空格 */
    				while (s--) { cout << " "; }
    			}
    
    			rt++;
    		}
    
    		cout << endl;
    		i++;
    	}
    }
    

    最后,改造三个递归函数,使之在递归调用时把结点信息存入“打印树”中。

    void fun11(int i, int n, PrintTree& t)
    {
    	if (i >= n)
    	{
    	}
    	else
    	{
    		t.addLeft(node(i + 1, i + 1));
    		fun11(i + 1, n, t);
    		t.addRight(node(i + 1, i + 1));
    		fun11(i + 1, n, t);
    	}
    }
    
    
    void fun22(int i, int n,PrintTree& t,int d)
    {
    	if (i >= n)
    	{
    	}
    	else
    	{
    		int k = i;
    		t.addLeft(node(d + 1, ++k));
    		fun22(++i, n, t, d + 1);
    		t.addRight(node(d + 1, ++k));
    		fun22(++i, n, t, d + 1);
    	}
    
    }
    
    void fun33(int& i, int n, PrintTree& t, int d)
    {
    	if (i >= n)
    	{
    	}
    	else
    	{
    		t.addLeft(node(d + 1, i+1));
    		fun33(++i, n,t,d+1);
    		t.addRight(node(d + 1, i+1));
    		fun33(++i, n,t,d+1);
    	}
    
    }
    
    4.2 运行测试,分别打印出fun1()、 fun2()、 fun3() 的递归过程。

    run:fun11();

    int main()
    {
    	PrintTree tr;
    
    	fun11(0, 3, tr);
    
    	tr.showTree(3);
    
    	return 0;
    }
    
    // 输出:
            0
          1   1
       2  2  2  2
    3 3 3 3 3 3 3 3
    

    run:fun22();

    int main()
    {
    	PrintTree tr;
    
    	fun22(0, 3, tr, 0);
    
    	tr.showTree(3);
    
    	return 0;
    }
    
    // 输出
            0
          1   2
       2  3  3  4
    3 4
    

    run:fun33();

    int main()
    {
    	PrintTree tr;
    
    	int a = 0;
    	fun33(a, 3, tr, 0);
    
    	tr.showTree(3);
    
    	return 0;
    }
    
    // 输出
            0
          1   6
       2  5
    3 4
    





    最后,如果觉得我的文章对你有帮助的话请帮忙点个赞,你的鼓励就是我学习的动力。如果文章中有错误的地方欢迎指正,有不同意见的同学也欢迎在评论区留言,互相学习。
    ——学习路上,你我共勉
    展开全文
  • 递归调用的理解

    2017-12-21 08:31:32
    递归是编程中一个相对难以理解但是却又很重要的概念. 对于从命令式语言开始学习编程的程序员天生对此有理解缺陷, 而对于从类似C++这种对函数式编程范式不友好的语言开始学习编程的程序员就更加如此了.(比如我自己) ...
  • 关于递归调用的深度

    千次阅读 2016-09-23 17:26:02
    1.对n个记录的线性表进行快速排序为减少算法的递归深度,以下叙述正确的是() 正确答案: A 你的答案: A (正确) 每次分区后,先处理较短的部分 每次分区后,先处理较长的部分 与算法每次分区后的...
  • 所以,代码中的递归调用部分就应该是递归求某一项的前边几项的和,不断递归去求和,直到递归到求1+2的和后,把和一层一层往上返回,不断加上该项的数得出新的和。 如果只有一项,那么前N项和就是1,所以变量m赋初值...
  • 递归调用(一)

    千次阅读 2016-06-27 09:53:46
    学习编程的时候老师总是不建议使用递归,一些书上至今也是这么建议的。但是递归在二叉树上的应用即优美又稍显复杂。所以弄清楚递归的本质是分治是很有必要的。将大规模问题缩小。 为什么要用递归 编程里面估计最...
  • 递归函数调用

    2020-02-01 18:43:46
    递归调用: 求n! . 如5!=5*4*3*2*1 =120 Int fac(int n) // 定义递归函数 { Int f; If(n<0) { } //n不能小于0 else if(n==0||n==1) //n=0或,1时n!=1 {...
  • 题目如下:问下列代码的打印结果为0吗? [cpp] view plaincopy #include  #include  using namespace std;    struct CLS  {   int m_i;   CLS( int i ) : m_i(i){...
  • 参照 #include int ...当n为0的时候停止递归,返回结果 由于遇到1的时候返回1,那么Func(1)=1 所以结果是5*(4*(3*(2*1))) = 120 转载于:https://www.cnblogs.com/guojiusong/p/8032306.html
  • //用递归求px(x,n)的值 #include<stdio.h> double px(double x,int n) { if(n==0) return 1; else return x*(1-px(x,n-1)); } int main() { printf(“please input the number of x,n\n”); i...
  • 从这个需求来看属于递归调用,也就是说先查出满足调价的省的记录,在本例子中的要查“辽宁省”的记录,如下: id   node_name parent_id 1   辽宁省  0   然后再查所有 parent_id 字段值为 1 的记录,...
  •  从这个需求来看属于递归调用,也就是说先查出满足调价的省的记录,在本例子中的要查“辽宁省”的记录,如下: id node_name parent_id 1 辽宁省 0  然后再查所有parent_id字段值为1的记录,如下: ...
  • 从这个需求来看属于递归调用,也就是说先查出满足调价的省的记录,在本例子中的要查“辽宁省”的记录,如下: id       node_name     parent_id 1           辽宁省               ...
  • SQL Server2005杂谈(2):公用表表达式(CTE)的递归调用  2010-04-20 16:30:51| 分类:SqlServer |字号 订阅 先看如下一个数据表(t_tree):  上图显示了一个表中的数据,这个表有三个字段:id...
  • 从这个需求来看属于递归调用,也就是说先查出满足调价的省的记录,在本例子中的要查“辽宁省”的记录,如下: id  node_name parent_id 1   辽宁省  0   然后再查所有 parent_id 字段值为 1 的记录,...
  • #include void main() { void hanoi(int n,char one,char two,char three); int n; printf("请输入需要移动的盘子数:\n"); scanf("%d",&n);...hanoi(n,'A','B','C');...void hanoi(int n,char one,char two,char three) ...
  • 递归

    2019-08-14 12:54:52
    每次递归调用会使问题逼近终止条件或情况,直到转化为该条件或情况为止。 (递归递归先递后归,递:层层递进只到最终条件为止,归:带着得到的结果一层层返回到原问题。题外话:翻译还是有点东西的) 递归的分类: ...
  • 从这个需求来看属于递归调用,也就是说先查出满足调价的省的记录,在本例子中的要查“辽宁省”的记录,如下: id  node_name parent_id 1   辽宁省  0   然后再查所有 parent_id 字段值为 1 的记录,...
  • 从这个需求来看属于递归调用,也就是说先查出满足调价的省的记录,在本例子中的要查“辽宁省”的记录,如下: id  node_name parent_id 1   辽宁省  0   然后再查所有 parent_id 字段值为 1 的记录,...
  • 算法第四版35页问题1.1.27,估计用一下代码计算binomial(100,50,0.25)将会产生的递归调用次数: public static double binomial(int n,int k,double p){ if(n == 0 && k == 0) return 1.0; if(n<0...
  • 从这个需求来看属于递归调用,也就是说先查出满足调价的省的记录,在本例子中的要查“辽宁省”的记录,如下: id  node_name parent_id 1   辽宁省  0   然后再查所有 parent_id 字段值为 1 的记录,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,315
精华内容 13,326
关键字:

下列属于递归调用的是