中职C语言中递归问题的解决方法探索

2022-09-11

递归就是一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法, 它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解, 从而大大地减少程序的代码量。用递归思想写出的程序往往十分简洁易懂。

一般来说, 递归需要有边界条件、递归前进段和递归返回段, 俗称为递推和回归。当边界条件不满足时, 递归前进;当边界条件满足时, 递归返回。有两个注意点: (1) 递归就是在过程或函数里调用自身; (2) 在使用递增归策略时, 必须有一个明确的递归结束条件, 称为递归出口。本文主要以两个常见实例, 对递归问题的解决方法进行探索, 从而加深大家对递归的理解。

1递归的编程方法

例1:用递归方法编一函数int yh (int m, int n) , 打印下图杨辉三角形。

分析:从杨辉三角形的特点可以知道, 左边一列也就是列坐标为0的时候, 值为1, 主对角线也就是行列相等的时候, 值为1, 其它值为上一行的前一列与上一行的同一列之和。由此可以知道, 递归结束条件就是当列坐标为0或者行列相等的时候, 返回1, 其它情况调用自身, 求得上一行的前一列与上一行的同一列之和。函数如下:

拓展:在实际运用中, 有很多这样的题目, 比如:求阶乘, 求Fibonacci数列, 求两个数的最大公约数, 汉诺塔问题等, 这类问题都可用递归的方法解决。遇到这类题目, 要找准两个注意点:一是递归出口, 即何时结束;二是自己调用自己, 要离结束条件越来越近。把握这两点, 类似的题目便能迎刃而解。

2递归程序的阅读

例2:阅读下列题目, 写出输出结果。

分析:这条题目的考点是大家对递归过程的了解情况, 函数ab () 有两个分支, 第一个分支是当y的值为0时, 输出x, 这是递归的出口;另一个分支是调用自己, 并输出x和y。输出结果的先后顺序是递归的难点, 考生往往容易出错, 程序阅读题, 阅卷老师通常是按行给分, 一旦输出顺序出错, 就会失分。那么如何理解, 才能不失分?阅读程序从主函数入手, 主程序的第一步是输出a和b的原始值36、24, 并调用函数ab (36, 24) ;由ab (36, 24) 推出y不为0, 做第二步ab (24, 12) , 并输出x、y的值为36、24, ……依此类推, 递归调用满足先调用后结束, 后调用先结束, 执行过程如图所示:

由图可知, 输出结果次序为:

拓展:若将函数ab () 中else后两句语句次序对调, 即改成先打印、后调用, 那么第一行的输出结果不变, 第二三四行的输出次序将倒过来。

从以上两个例题可以看出, 递归题目其实并不难, 关键要理解递归的方法, 把握两个注意点:一是递归出口, 即何时结束;二是自己调用自己, 要离结束条件越来越近。同时, 要理解递归的执行过程, 递归前进段和递归返回段。那么, 做递归的题目才能得心应手, 广大编程爱好者要多总结, 从而对循环及分支语句的使用能有进一步的了解。

摘要:递归是各类高级语言中的一个重要知识点, 如果理解透彻, 解决问题就会得心应手, 反之会与循环语句混淆, 甚至在写输出结果时, 秩序完全相反。本文主要以C语言为例, 介绍一些常见递归题目的编程和解决方法, 从而加深大家对递归的了解。

关键词:C语言,递归

参考文献

[1] 卢宇清.C语言程序设计教程[M].清华大学出版社, 2009.

[2] 石远东.计算机专业综合理论复习用书 (上册) 第二版[M].原子能出版社, 2007.