首页 > Java > java教程 > 正文

递归-1

王林
发布: 2024-08-25 18:00:32
原创
631 人浏览过

简介1

函数调用自身的过程称为递归,
相应的函数称为递归函数.
由于计算机编程是数学的基本应用,所以让
我们首先尝试理解递归背后的数学推理。
一般来说,我们都知道函数的概念。简而言之,函数是
提供输入时产生输出的数学方程。例如:
假设函数 F(x) 是由下式定义的函数: F(x) = x^2 + 4
我们可以将此函数的 Java 代码编写为:

public static int F(int x){
返回 (x * x + 4);
}

现在,我们可以将不同的 x 值传递给该函数并接收我们的输出
相应地。
在继续递归之前,让我们尝试理解另一个数学
称为数学归纳原理(PMI)

的概念

数学归纳原理(PMI)是一种证明陈述的技术,
公式,或关于一组自然数的定理。它有
以下三个步骤:
1.** 小案例的步骤*:在这一步中,我们将证明
所需的陈述 基本情况,例如 n = 0 或 n = 1。
2.
* 假设步骤**:在这一步中,我们将假设所需的语句
对于 n = k 有效。

  1. 证明步骤:根据假设步骤的结果,我们将证明, 只要 n = k 为真,n = k + 1 对于所需方程也成立。

例如:让我们用数学归纳法证明:
S(N): 1 + 2 + 3 + ... + N = (N * (N + 1))/2
(前N个自然数之和)
证明:
步骤 1:对于 N = 1,S(1) = 1 为真。
步骤 2:假设,对于 N = k,给定的陈述成立,即
1 + 2 + 3 + .... + k = (k * (k + 1))/2
步骤 3:让我们使用步骤 2 来证明 N = k + 1 的命题。

证明:1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
证明:

将第 2 步得到的结果中的 LHS 和 RHS 添加 (k+1):
1 + 2 + 3 + ... + (k+1) = (k*(k+1))/2 + (k+1)

现在,从 RHS 端取 (k+1) 个公共:
1 + 2 + 3 + ... + (k+1) = (k+1)*((k + 2)/2)

根据我们试图证明的陈述:
1 + 2 + 3 + ... + (k+1) = ((k+1)*(k+2))/2
由此证明。

递归的工作

总结以上三点,我们就可以定义递归方法的步骤
步骤:
● 基本情况:递归函数必须有一个终止条件,在该条件下
该进程将停止调用自身。这种情况称为基本情况。如果没有基本情况,它会不断调用自己并陷入
无限循环。很快,就会超出递归深度*并抛出
错误。
● 递归调用:递归函数将在较小的版本上调用自身
的主要问题。我们在编写此步骤时需要小心
对于正确找出你的小问题是什么至关重要。
● 小计算:一般我们在每个递归中执行一次计算步骤
称呼。我们可以在递归调用之前或之后实现这个计算步骤
取决于问题的性质。

注意:递归使用存储递归调用的内置堆栈。因此,
递归调用的次数必须尽可能少,以避免内存溢出。如果
递归调用次数超过最大允许数量,
**将超过递归深度
**。
现在,让我们看看如何使用递归解决一些常见问题

问题陈述 - 求一个数的阶乘

方法:找出 PMI 的三个步骤,然后使用
将其关联起来 递归

  1. 归纳步骤:计算数字 n - F(n) 的阶乘 归纳假设:我们已经得到了 n-1 - F(n-1)
  2. 的阶乘
  3. 用 F(n-1) 表示 F(n):F(n)=n*F(n-1)。因此我们得到

public static int fact(int n){
int ans = 事实(n-1); #假设步骤
返回 ans * n; #从假设步骤解决问题
}

  1. 代码尚未完成。缺少的部分是基本情况。现在我们将 试运行以查找需要停止递归的情况。考虑 n = 5:

Recursion -1

正如我们在上面看到的,我们已经知道 n = 0 的答案,即 1。所以我们将
将此作为我们的基本情况。因此,代码现在变成:

公共静态 int 阶乘(int n){
if (n == 0) // 基本情况
返回 1;
其他
返回 n*阶乘(n-1); // 递归情况
}

以上是递归-1的详细内容。更多信息请关注PHP中文网其他相关文章!

来源:dev.to
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板