关于递归的一些简单想法

我的主力博客:半亩方塘

递归是我们在编程过程中用到的一种思想,当一个函数自身调用自身的时候,无论是直接或者间接地调用,都属于递归,下面对于什么时候用到递归以及怎么用递归,谈一点我个人初步的想法。

  1. 什么时候用到递归
    当我们要解决的问题有着 重复执行的基本操作 的时候,可以考虑使用递归
  2. 用递归思想进行编程的时候需主要需要注意的几点内容
    首先是 递归上限 ,通常是一个指出递归开始位置的 有效范围内 的对象,一般作为主调函数传输的参数;其次是递归下限 ,主要用来确定结束递归的操作,一定要有退出递归的标志性操作,否则,递归将无限期地进行下去;最后就是确定实现递归的 基本操作 和 由递归上限到递归下限的变化过程 ,基本操作在确定使用递归的时候已经考虑好了,需要特别考虑的是由递归上限到递归下限的变化过程,极易出错

    下面通过两个例子来加深对上面这段话的理解(C++ 实现):

    (1)求一个数的阶乘

    首先,是不是可以用到递归?求一个数的阶乘的时候,重复涉及到两个数的乘法,这是一个 重复执行的基本操作,由此确定此问题可以用递归实现;其次,递归上限是什么?因为阶乘实现的是从 1 到这个数之间所有数的累乘,所以, 递归上限 就是这个数本身,同样可以得到递归下限是 1,最后,需要确定从递归上限到递归下限的变化过程,显然,这个变化过程就是这个数本身(递归上限)到 1(递归下限) 之间不断减 1 的过程,也就是主调函数传输的参数不断减 1 的过程,经过以上分析后,很轻松地就可以写出下面的代码

    #include using std::cin; using std::cout; using std::endl; // 实现阶乘操作的递归函数 int factorial (int val) { if (val > 1) return factorial(val - 1) * val; // val - 1 使得递归上限向递归下限不断接近 else // 其实 else 也可以不写,想想为什么? return 1; } int main() { int ival = 0; cout > ival; int res = factorial(ival); cout

    对于上面的代码,实现阶乘操作的递归函数中,else 可以不写,因为,当传递给 factorial 的参数等于 1 时,函数返回 1 后,结束递归,进入倒数第二层的 factorial 函数的执行,倒数第二层 return factorial(val - 1) * val 之后,即结束倒数第二层的函数调用,在没有 else 的情况下,并不会执行到 return 1,其他层的调用同理,所以,不需要 else ,程序也是正确的,这里写上 else ,只不过为了使得程序的逻辑结构更加清晰一些,另外,return factorial(val - 1) * val 中的 val - 1 切不可换为 --val,如果换成 --val 的话,改变的不仅仅是传递给下一层 factorial 的参数 val,连同本层的 val 也一起改变了,无疑这将引起错误。
    (2) 输出 vector 对象的内容
    首先,是不是可以用递归呢?要不断输出 vector 对象的内容,这就是一个 重复执行的基本操作 ,因此可以用递归思想进行实现,其次,递归的上限是什么呢?有人说,是 vector 对象尾后元素的指针,可是,真的是这个吗?这是不对的,尾后元素的指针并不指向一个有效范围内的对象,它指向的存储空间存储的值是未定义的,这一点尤其要注意,所以,真正的递归上限应该是 vector对象的尾后指针减 1 ,这才是真正有效范围内的对象,显然,递归下限是指向 vector 对象首元素的指针,最后,从递归上限到递归下限的变化过程是递归上限不断减 1 向递归下限逼近,直至最后等于递归下限的值为止,同样轻松地写出了以下的代码

    #include #include using std::cin; using std::cout; using std::endl; using std::vector; // 实现打印 vector 对象元素的递归函数 void print(const vector &vec, decltype(vec.begin()) ibeg, decltype(vec.begin()) iend) { if (iend != ibeg) print(vec, ibeg, iend - 1); // iend - 1 使得递归上限向下限不断逼近 cout ivec; int ival; cout > ival; ivec.push_back(ival); } // 打印这 10 个数 print(ivec, ivec.begin(), ivec.end() - 1); // 真正的递归上限应该是 vector 对象的尾后指针减 1 cout

    同理,在实现打印 vector 对象元素的递归函数中 iend - 1 不能换成 --iend,因为这样会改变本层函数中的 iend 参数的值,会得不到期望中的结果,形参中 vector 对象的类型是引用类型,避免了拷贝所引起的时间效率低下和存储空间的浪费,同时,使用 const 是因为不需要改变元素的值,仅仅对元素进行输出操作
    以上是我对于递归思想运用的一些简单想法,随着以后逐步深入的了解会有相应的博文推出,欢迎提供宝贵意见。

    点击复制链接 与好友分享!回本站首页
    您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
    上一篇:对文本框的输入限制
    下一篇:smarty中foreach的使用
    相关文章
    图文推荐

    关于递归的一些简单想法
    适配器模式
    关于递归的一些简单想法
    Handler的介绍和使用
    关于递归的一些简单想法
    struts2上传文件
    关于递归的一些简单想法
    通过JFreeChart的饼状

分类:默认分类 时间:2015-02-27 人气:2
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.145 (s). 9 q(s)