精华内容
下载资源
问答
  • 刚刚学习了递归调用的知识,觉得递归这种算法真是太妙了。 递归算法:优点:定义清晰,容易证明其正确性和完备性; 缺点:1、资源消耗大;一个最简单的递归,其每次调用都至少消耗8B空间(这里是关于形参实参值...

        刚刚学习了递归调用的知识,觉得递归这种算法真是太妙了。

        递归算法:优点:定义清晰,容易证明其正确性和完备性;

                         缺点:1、资源消耗大;一个最简单的递归,其每次调用都至少消耗8B空间(这里是关于形参实参值传递的问题,详细可以参考本人的第一篇博客,https://blog.csdn.net/weixin_41978722/article/details/79921816#0-qzone-1-39788-d020d2d2a4e8d1a374a433f596ad1440),若不控制其递归深度,就很容易造成系统堆栈的溢出,使系统崩溃。

                                    2、会出现大量重复运算。(如斐波那契数列:

                                                                                int fibonacci(int n) {

                                                                                    return n<=2? 1:fibonacci(n-2)+fibonacci(n-1);     }        )


        下面,通过一例题来表现一下递归算法:八皇后问题。

        根据所学,递归要考虑  1.相同操作   2.思考简单  3.递归结束条件


        看到问题,不要急于编程,“手工过程”很重要!如果我们面前有一个棋盘,我们要怎样摆?


        1、按照一般人的思维,一行一行来;第一个皇后放到第一行第一列上(1,1),下一个皇后必然在第二行放置,放置同样从第一列开始考虑,直到该棋子安全(其左上,上,右上方向均无棋子),则开始下一行;

        2、若这一行没有安全位置,就必须返回上一行,继续移动上一行的棋子找到该棋子下一个安全位置,以此类推;

        3、结束条件:找到最后一行的安全位置,即第8行,结束!

        所以每次递归操作只需考虑此时自己这一行就好!


        那么,棋盘如何表示?        二维数组!   8*8方阵,咱们用1代表放置棋子,0代表没有放置棋子。


        程序主要函数如下:

        

    void orderQueen(int (*chessboard)[8], const int row) 	  // 在当前行只需要考虑当前行!
    {	
    	if (row >= 8) 
    	{
    		drawChessboard(chessboard);
    	} else {
    		int col;
    		
    		for (col = 0; col < 8; col++) // 尝试每一列
    		{ 
    			chessboard[row][col] = 1;		// 放置皇后
    			if (isSafe(chessboard, row, col)) // 若本行本列是安全的
    			{ 
    				orderQueen(chessboard, row + 1); // 放置下一行
    			}
    			chessboard[row][col] = 0;		// 无论本行列是安全或者不安全的,都需要去掉本位置的皇后!因为,下列需要放置一个皇后!
    		}
    	}
    }
    
    void drawChessboard(int (*chessboard)[8]) 
    {
    	int row;
    	int col;
    	static int count = 0;
    	
    	printf("第%d个解:\n", ++count);
    	for(row = 0; row < 8; row++)      //输出棋盘
    	{
    		for(col = 0; col < 8; col++) 
    		{
    			printf("%2d", chessboard[row][col]);
    		}
    		printf("\n");
    	}
    }
    	
    int isSafe(int (*chessboard)[8], const int row, const int col) 
    {
    	int i;
    	int j;
    	
    	for (i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)    //判断左上方向有无棋子
    	{
    		if (chessboard[i][j] == 1) 
    		{
    			return 0;
    		}
    	}
    	for (i = row - 1, j = col; i >= 0; i--)                       //判断上方有无棋子
    	{            
    		if (chessboard[i][j] == 1) 
    		{
    			return 0;
    		}
    	}
    	for(i = row - 1, j = col + 1; i >= 0 && j < 8; i--, j++)     //判断右上方有无棋子
    	{
    		if (chessboard[i][j] == 1) 
    		{
    			return 0;
    		}
    	}
    	
    	return 1;    
    }
    
        如果无法理解此行判断完没有安全位置返回上一行操作的,怎么说呢?通俗点说递归他是一层套一层的,如果这层判断完自然就回到了上一层,若还是没有理解,可能在我表述不清;建议自己画棋盘用棋子对照程序变量跟踪,这就很好理解了!
    展开全文
  • 从几道简单的例题递归 写在前面 递归三要素:边界条件,递归前进段,递归返回段。递归作为最基础算法之一,最常见表现形式就是函数直接调用自身。递归的难点在于如何设计“退路”,也就是找到边界条件,处理...

    从三道例题谈谈递归

    写在前面

    递归三要素:边界条件,递归前进段,递归返回段。递归作为最基础的算法之一,最常见的表现形式就是函数直接调用自身。递归的难点在于如何设计“退路”,也就是找到边界条件,处理好递归返回段。本文将从三道例题出发简单聊聊递归。

    例题一:阶乘

    给定一个正整数n,求它的阶乘n!,即 n * (n-1) * (n-2)……* 2 * 1

    这是一道想法直观、实现简单的运用递归的例题

    我们用F(n)来表示n的阶乘,那么 F(n)=n * F(n-1)


    1. 首先明确边界条件,当某层递归F(m)中m不等于1时,继续执行递归前进段,在F(m)中调用F(m-1)
      在这里插入图片描述
    2. 到达F(1)后,开始执行递归返回段,也就是退路
      在这里插入图片描述

    C语言代买如下

    int F(int n)
    {
    	if (n != 1)
    		return n * F(n - 1);
    	else
    		return 1;
    }
    

    例题二:快速幂

    编写函数myPow(double x, int n),实现计算x的n次幂
    其中,x∈[-100.0,100.0],n∈[-231,231-1]

    一个简单粗暴的想法是逐个相乘,比如 28=2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

    但是可以进一步优化,如果已经求得 24,只需将这个数求平方就能得到结果;而如果已经求得 22,也只需将其平方就能得到24

    这样,我们自然就有了运用递归的想法


    这道题的边界条件也很明显

    我们用F(n)来表示xn,那么F(n)=[F(n/2)]2,而F(n/2)=[F(n/2/2)]2,依次类推,直到F(2) = [F(1)]2,到达边界,开始执行递归返回段

    我们以26为例,画出递归的过程如下:

    1. 递归前进段
      在这里插入图片描述
    2. 在上图中,由于整型运算中3 / 2 = 1,而[F(1)]2=F(2)而不是我们想要的F(3),所以这个程序中还有一个很重要的设计:在递归返回段中,判断当前得到的幂是否是所期望的,如果不是,只需再乘以一个底数x
      在这里插入图片描述
      C语言代码如下
    //递归函数
    //value_current是当前值,pow_expect是当前所期望的次幂
    int Recurse(double x, int n, double *value_current, int pow_expect)
    {
    	int pow_current = 1;	//当前次幂
    	
    	if (pow_expect != 1)	//边界条件
    	{
    		pow_current = Recurse(x, n, value_current, pow_expect / 2);	//递归前进段
    	}
    
    	if (pow_current == pow_expect - 1)	//当前次幂与当前所期望次幂不相等,需要补充乘以一个底数x
    	{
    		(*value_current) *= x;
    	}
    
    	if (pow_expect != n)	//递归返回段
    	{
    		(*value_current) *= (*value_current);
    		return pow_expect * 2;
    	}
    
    	return -1;	//递归结束
    }
    
    double myPow(double x, int n)
    {
    	double value_current = x;
    	int n_symbol = 1;	//指数n的符号
    	int int_min_flag = 0;
    
    	//特殊值判断
    	if (x == 0)
    		return 0;
    	else if (x == 1)
    		return 1;
    	else if (x == -1)
    	{
    		if (n % 2)
    			return -1;
    		else
    			return 1;
    	}
    
    	//因为n的取值可能是-2^31,将其符号取反后是2^31,超过了int的取值范围,所以要进行一些操作
    	if (n == INT_MIN)
    	{
    		n += 1;
    		int_min_flag = 1;
    	}
    
    	if (n < 0)
    	{
    		n_symbol = -1;
    		n = -n;
    	}
    	else if (n == 0)
    	{
    		return 1;
    	}
    
    	Recurse(x, n, &value_current, n);
    
    	if (int_min_flag)
    	{
    		value_current *= x;
    	}
    
    	if (n_symbol == 1)
    		return value_current;
    	else
    		return 1/value_current;
    }
    

    例题三:生成有效括号

    这是LeetCode题库中的22题,原题如下:

    给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

    例如,给出 n = 3,生成结果为:
    [
    “((()))”,
    “(()())”,
    “(())()”,
    “()(())”,
    “()()()”
    ]


    明确边界条件

    在生成括号的过程中,
    (1)左括号数>=右括号数
    (2)左括号数/有括号数<=n

    当边界条件都满足时,执行递归前进段。本题中,递归前进段的设计是:能放置左括号就先放置左括号,然后再放置右括号。

    当任一边界条件不满足时,就进入递归返回段。本题中的退路设计是:去掉最后放置的括号。


    为了叙事方便,我们以n=2为例,画出递归的过程如下:

    1. 执行递归前进段,能放置左括号就先放置左括号
      在这里插入图片描述

    2. 连续放置3个括号后,不满足边界条件2,进入递归返回段,去掉最后放置的括号,返回((后又进入递归前进段,添加右括号
      在这里插入图片描述

    3. 同上,此处得到了第一个有效的排列组合(()),之后再进入递归前进段得到的排列组合都将违反边界条件2,所以将一路返回到(
      在这里插入图片描述

    4. (的右支与左支大同小异
      在这里插入图片描述

    5. 得到第二个有效的排列组合()()
      在这里插入图片描述

    6. 右括号的数量大于左括号的数量,不满足边界条件1

    在这里插入图片描述

    至此,我们得到了n=2的全部有效的括号的排列组合:(())()()


    C语言代码如下

    //递归函数
    //一维字符数组temp用于临时存放正在生成中的括号的组合,left_num、right_num是当前左、右括号数量
    int Recurse(char *temp, int *temp_index, char **ret, int *ret_row, int n, int *left_nums, int *right_nums)
    {
    	if (*left_nums < n)	//边界条件
    	{
    		temp[*temp_index] = '(';	//递归前进段1:放置左括号
    		(*temp_index)++;
    		(*left_nums)++;
    		Recurse(temp, temp_index, ret, ret_row, n, left_nums, right_nums);
    		temp[*temp_index] = '\0';	//递归返回段:去掉最后放置的括号
    		(*temp_index)--;
    		(*left_nums)--;
    	}
    
    	if (*right_nums < *left_nums)	//边界条件
    	{
    		temp[*temp_index] = ')';	//递归前进段2:放置右括号
    		(*temp_index)++;
    		(*right_nums)++;
    		Recurse(temp, temp_index, ret, ret_row, n, left_nums, right_nums);
    		temp[*temp_index] = '\0';	//递归返回段:去掉最后放置的括号
    		(*temp_index)--;
    		(*right_nums)--;
    	}
    
    	if (*left_nums == n && *right_nums == n)	//左括号数=有括号数=n,则生成了有效的排列组合
    	{
    		ret[*ret_row] = (char *)malloc((2 * n + 1) * sizeof(char));
    		strcpy(ret[*ret_row], temp);	//将有效的排列组合复制到二维字符数组ret中
    		ret[*ret_row][2 * n] = '\0';
    		(*ret_row)++;
    	}
    
    	return 0;
    }
    
    char ** generateParenthesis(int n, int* returnSize) 
    {
    	char *ret[20000];
    	char *temp = (char *)malloc((2 * n + 1) * sizeof(char));
    	int left_nums = 0, right_nums = 0, ret_row = 0, temp_index = 0;
    	
    	Recurse(temp, &temp_index, ret, &ret_row, n, &left_nums, &right_nums);
    	*returnSize = ret_row;
    
    	free(temp);
    
    	return ret;
    }
    

    结语

    正如开头所说,递归的难点在于如何找到边界条件、如何设计退路

    在前两到例题中,递归仿佛像是一个“上下井”的过程,递归前进段是沿着井往下走,边界条件是井底,触到井底后就一直往上走,即递归返回段

    但第三道例题有在井里反复上下的感觉,原因是在Recurse()函数中两次调用自身,与二叉树的深度优先遍历十分相像。

    本文意在与大家聊聊我在学习递归时的一些心得体会,如有疏漏,望指正

    展开全文
  • 递归调用图例

    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、函数式简介2、匿名函数与lambda二、递归调用1、递归调用要点透析2、递归调用的两个过程:回溯与递推3、递归经典例题练习(1)嵌套多层的列表,要求打印出所有的元素(2)二分法递归实现 ...
  • 递归,是一种函数调用,简单来说,函数内容无非就是两部分,第一部分是出口,另一部分则是循环调用的语句。下面,可以通过具体的函数来理解什么是递归。 1.阶乘: double fact(int n) { if (n == 1 || n == 0) ...

    关于C语言递归函数的心得及一些例题

    递归,是一种函数调用,简单来说,函数内容无非就是两部分,第一部分是出口,另一部分则是循环调用的语句。下面,可以通过具体的函数来理解什么是递归。
    1.阶乘:

    double fact(int n) {
    	if (n == 1 || n == 0)
    		return 1;
    	else return(n * fact(n - 1));
    }
    

    2.指数函数:

    /*x是底数,n是指数*/
    double calc_pow(double x, int n) {
    	if (n == 1)
    		return x;
    	else return (x * calc_pow(x, n - 1));
    }
    

    3.Fabonacci数列:

    /*f返回第n个斐波那契数列*/
    int f(int n) {
    	int sum;
    	if (n == 0) {
    		sum = 0;
    	}
    	else if (n == 1) {
    		sum = 1;
    	}
    	else {
    		sum = f(n - 2) + f(n - 1);
    	}
    	return sum;
    }
    

    4.顺序输出整数:

    void printdigits(int n) {
    	if (n < 10) {//出口
    		printf("%d\n", n);
    	}
    	else {
    		printdigits(n / 10);//12345-1234-123-12-1-12%10-123%10-1234%10-12345%10
    		printf("%d\n", n % 10);
    	}
    }
    

    5.十进制换二进制:

    void dectobin(int n) {
    	if (n == 0) {
    		printf("0");
    	}
    	else if (n == 1) {
    		printf("1");
    	}
    	else {
    		dectobin(n / 2);//10-5-2-1  1-1 2-0 5-1 10-0
    		printf("%d", n % 2);
    	}
    }
    
    展开全文
  • 利用递归可以用简单的程序来解决一些复杂问题。它通常把一个大型复杂问题层层转化为一个与原问题相似规模较小问题来求解,递归策略只需少量程序就可描述出解题过程所需要多次重复计算,大大地减少了程序...
  • 在leetcode练习也练了一段时间了,在解决问题过程中,我们经常会用到那些算法思想呢,今天就来总结一下,我遇到算法思想总结 递归:反复利用自身以解决问题 ...在递归调用过程中,系统用栈来存储每一层返回点和
  • 递归

    2021-03-29 15:26:08
    ​ 利用递归可以用简单的程序来解决一些复杂问题。通常把一个大型复杂问题层层转化为一个与原问题相似规模较小问题来解决,递归策略至于要少量程序就可以描述出结题过程所需要多次重复计算,大大减少...
  • 基础算法之简单递归

    2015-03-27 23:15:00
    递归算法简单来说就是把问题规模缩小然后递归调用。其中有三个经典例题,汉诺塔,阶乘,与斐波那契数列。这里只写一个阶乘例子,递归调用还会在以后详细讨论。 #include<stdio.h> int iJiecheng(int a); ...
  • 典型的递归问题

    2020-12-15 13:14:48
    递归可以使复杂问题简单递归是函数调用自己本身函数的调用会在栈上开辟内存 对于递归来说核心是找到递归公式和递归终止条件假如终止条件找错会出现StackOverFlowError错误 经典例题1: 汉诺塔问题 先来分析一下: ...
  • 在程序中的递归,便是是函数自己直接或间接的调用自己。在面对一个大问题时我们很难去解决,但是我们可以将其分成一个个类似小问题去解决,最终求出大问题。 递归的关键: 一.递归需要终止条件(出口) 二.找出...
  • 递归法和分治法一、递归与堆栈二、基于归纳的递归三、递推关系求解四、分治法1、基本思想五、例题一、递归例题简单例题中等例题困难例题二、分治例题简单例题中等例题困难例题 一、递归与堆栈 1、递归(recursion)是...
  • js递归函数递归思想

    2021-01-20 12:27:15
    递归是编程算法一种,通过调用自身,将一些复杂/抽象问题简单化,便于得出解决方案。 先看一道题: 例题:某人需要走上10级台阶,有两种走法,走法A:一步1个台阶;走法B:一步2个台阶。两种走法可以任意交替...
  • javaSE 之 递归 详解

    2019-10-20 20:12:27
    递归的效率很低,能不用就不用,但是很多方法用递归简单,比如例题的阶乘 注意看例题的阶乘内存分析 对于九九乘法表的例题,俩种方式都可以,目的就是为了在递归时候结束递归 什么是递归? 递归就是自己调用...
  • 5_递归

    2021-02-19 03:27:43
    程序调用自身编程技巧称为递归递归的实质是将问题转化为规模更小相同问题。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。 它思想...
  • 递归和循环

    2020-12-16 21:10:25
    递归 :在一个函数内部调用这个函数自身 循环 :通过设置计算初始值及终止条件,在一个范围内重复运算。 通常递归的代码会比较简洁,但效率低,且很多计算都是重复例题 递归和循环性能区别 面试题10 - I ...
  • 递归函数

    2020-04-12 22:03:01
    1.递归函数含义:直接或间接...} 定义与调用与普通函数是类似的,一般只将规模很小而频繁使用的简单函数声明为内联函数 3.函数重载:一个程序中,可以定义多个具有相同函数名,不同参数列表的函数,编译系统将通...
  • C语言——递归(一)

    2020-10-22 19:12:58
    (2)递归调用必须有一个结束条件,否则递归调用就无法结束了; 例题: 一、递归求幂; 核心代码: if(m==0) return 1; y=power(x,m/2); y=y*y; if(m%2!=0) y=y*x 完整代码: #include<stdio.h> ...
  • 递归的定义 在定义一个过程或者函数时出现调用本过程或函数的成分成为递归。...2.递归调用的次数必须是有限的。 3.必须有结束递归的条件来终止递归。 例题 【例1】以下是求n!的递归函数。 int fun(int
  • 递归的定义:在一个函数里再调用这个函数本身 递归的最大深度默认是:997 - - 是python从内存角度出发做限制 递归的缺点: 占内存 递归的优点: 会让代码变简单 1.1 测试递归最大深度 n = 0 def recursion(): ...
  • 递归函数(迭代)

    2021-03-10 21:06:37
    递归函数作为一大重要算法,在我们平时编程过程中会经常被用到,在这里我将我寒假学习递归函数心得分享给大家,并引用几道比较简单的例题帮助我们去理解递归函数。 前n个数和/积 我们首先要进行思考,前n项...
  • 递归与栈

    千次阅读 2017-07-25 10:30:13
                                ——《岳阳楼记》一、递归:  简单来说,递归就是自己调用自己,然后一层一层返回。   所有for循环都可以用递归来做。废话不多说,直接上例题:1、...
  • 这句经典名言体现了递归算法重要性,虽然执行效率不如迭代法,但它可以使那些很复杂问题化成简单化。 什么是递归呢? 把一个直接调用自己或通过一系列的调用语句间接地调用自己函数,称为递归函数。简言之:在...
  • 例题一:最简单的递归: #include<stdio.h> int main() { printf("hehe\n"); main(); return 0; } //递归常见错误:stack overflow 内存分为栈区(局部变量,函数形参,函数调用),堆区(动态开辟...
  • 五大经典算法一 递归与分治

    万次阅读 2017-03-21 12:06:30
    递归算法:直接或者间接不断反复调用自身来达到解决问题方法。要求原始问题可以分解为相同问题子问题。、 需要: 1 递归边界 2 自身调用 特点分析: 递归思路简单清晰,如果分析出将很快得到结果;递归将多次调用...
  • 从一个简单例题开始3. 递归与分治真好吗?3.1 线性衰减递推式3.2 比例衰减递推式4. 最后说几句 1. 简介 递归与分治,顾名思义,就是既有递归又有分治。递归指函数调用自身,分治是指一个大问题被分成了几个...
  • 我们用一个简单的例题演示: ∑k=1n\displaystyle\sum_{k=1}^nk=1∑n​ K #include<stdio.h> #include<stdlib.h> #include<math.h> int ans=0; int sum(int n) { if(n!=0) { ans = ans + n; n...
  • 本题目摘自C语言网,简单的C语言例题。 题目: 利用递归函数调用方式,将所输入5个字符,以相反顺序打印出来。 1.程序分析: 利用递归函数调用方式。 2.程序源代码: #include “stdio.h” main() { int ...

空空如也

空空如也

1 2 3
收藏数 47
精华内容 18
关键字:

递归调用的简单例题