瞎扯淡:聊聊递归

本贴最后更新于 2868 天前,其中的信息可能已经东海扬尘

递归的定义

  • 根据 wiki 百科,递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

递归的实现机制

  • 在一些编程语言里,递归机制的实现数据模型是堆栈,即后进先出的数据结构。下图展示了递归的调用栈,一次递归可以分解为入栈及出栈两步,蓝色箭头线展示了入栈的过程,直到达到退出条件,则转为红色线表示的出栈过程,并一步步推算得出结果。

5a9f477be9944cfb810b9cf9819db9ce-digui.png

简单的递归(求阶乘)

  • 一些问题,可以轻易的写出递归,比如求阶乘

public int f(int n){
  if(n < 2 ){
	return n;
  }else{
	return n * f(n - 1);
  }
}

组合使用递归

  • 更多的问题,使用无法使用单个递归解决,而是要组合使用递归思想,比如递归求简单交错幂级数的部分和:
public double sum( double x, int n){
  if(n == 1){
	return x;
  }else{
  return mult(x, n) + sum(x, n -1);
  }
}

public double mult( double x, int n ){
  if(n == 1 ){
	return x;
  }else{
	return (-1) * x * mult(x, n - 1);
  }
}
  • 上述代码中,sum()方法作为递归方法,调用了另外一个递归方法 mult(),通过递归的嵌套组合使用,来完成简单交错幂级数的部分和计算。

递归的特点

  • 1、是处理逻辑的抽象,抽象程度高,能解决常规方法所不能解决的问题。

  • 2、内存消耗大、计算成本高,由于要在内存里记录每一层返回点和局部变量。它的计算规模和能力取决于内存和 cpu 的能力。

  • 递归
    15 引用 • 9 回帖
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3187 引用 • 8213 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...