郝斌数据结构4递归

我会带着你远行 2022-03-02 12:14 252阅读 0赞

1 定义  
一个函数自己直接或间接调用自己  
2 举例

#include <stdio.h>
    #include <stdlib.h>
    
    void f(int n)
    { 
    	if (1 == n)
    	{ 
    		printf("哈哈\n");
    	}
    	else
    	{ 
    		f(n-1);
    	}
    }
    
    int main(void)
    { 
    	f(7);
    	return 0;
    }

运行结果  
![在这里插入图片描述][20190320143921139.png]  
3 n的阶乘用递归来实现  
3.1 如果不用递归来实现

#include <stdio.h>
    #include <stdlib.h>
    
    int main(void)
    { 
    	int i,n,mul = 1;
    	printf("请输入n的值:");
    	scanf("%d",&n);
    	for(i = 1;i <= n;i++)
    	{ 
    		mul = mul * i;
    	}
    	printf("mul = %d\n",mul);
    
    	return 0;
    }

![在这里插入图片描述][20190320144025330.png]  
3.2 如果用递归来实现

#include <stdio.h>
    #include <stdlib.h>
    
    int f(int n)
    { 
    	if(1 == n)
    	{ 
    		return 1;
    	}
    	else
    	{ 
    		return f(n-1) * n;
    	}
    }
    
    int main(void)
    { 
    	int n;
    	printf("请输入n的值:");
    	scanf("%d",&n);
    	printf("n的阶乘是:\n%d\n",f(n));
    	
    	system("pause");
    	return 0;	
    }

![在这里插入图片描述][2019032014413269.png]  
4 1+2+3+…+100之和用递归来实现  
4.1 不用递归实现  
4.2 用递归实现

#include <stdio.h>
    #include <stdlib.h>
    
    int f(int n)
    { 
    	if(1 == n)
    	{ 
    		return 1;
    	}
    	else
    	{ 
    		return f(n-1) + n;
    	}
    }
    
    int main(void)
    { 
    	printf("1到100的和是:\n%d\n",f(100));
    	
    	system("pause");
    	return 0;	
    }

![在这里插入图片描述][20190320144242308.png]  
5 一个函数为什么可以自己调用自己  
函数的调用:  
当在一个函数的运行期间调用另一个函数时，在运行被调函数之前，系统需要完成三件事:

1.  将所有的实际参数，返回地址等信息传递给被调函数保存
2.  为被调函数的局部变量（包括形参）分配存储空间
3.  将控制转移到被调函数的入口  
    从被调函数返回主调函数之前，系统也要完成三件事:
4.  保存被调函数的返回结果
5.  释放被调函数所占的存储空间
6.  依照被调函数保存的返回地址将控制转移到调用函数

当有多个函数相互调用时，按照“后调用先返回”的原则，上述函数之间信息传递和控制转移必须借助“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就在栈顶分配一个存储区，进行压栈操作，每当一个函数退出时，就释放它的存储区，进行出栈操作，当前运行的函数永远在栈顶位置。

A函数调用A函数和A函数调用B函数在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而已！

例子: 间接调用自己举例

#include<stdio.h>
    void g(int);
    
    void f(int n)
    { 
    	g(n);
    }
    void g(int m)
    { 
    	f(m);
    }
    int main(void)
    { 
    	return 0;
    }

6 递归必须满足三个条件

1.  递归必须得有一个明确的终止条件
2.  该函数所处理的数据规模必须在递减
3.  这个转化必须是可解的

例子: 递增的值可以增加，但处理的数据的规模需要递减

#include<stdio.h>
    int f(int n)
    { 
    	if(n>7)
    		printf("哈哈\n");
    	else
    		n=f(n+1);
    	return n;
    }
    
    int main(void)
    { 
    	int val;
    	val=f(5);
    	printf("val=%d\n",val);
    	return 0;
    }

解析: 如下图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20190320144854539.png]  
7 循环和递归的比较  
理论上，所有的循环都可以转化成递归，但是用递归能解决的问题不一定能用循环解决。  
递归:  
易于理解，速度慢，存储空间大  
循环:  
不易理解，速度快，存储空间小

[20190320143921139.png]: /images/20220302/c60129b491284f4dbdac042da246830a.png
[20190320144025330.png]: /images/20220302/b18da6dd881545a684b1afaae30d55e3.png
[2019032014413269.png]: /images/20220302/dbfb1102ecf748bb9630548028a8b7d1.png
[20190320144242308.png]: /images/20220302/936e1dab78cd426f88eb0827445c87fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]: /images/20220302/7b60c5e4284d4bdb8b2d95f412b468f2.png
[20190320144854539.png]: /images/20220302/3df71687be694b779346d6f36ed8975f.png