c语言递归递推

标签：return 语言递归 int sumRecursive1 fibonacci ff 递推

1、递推与递归

https://blog.csdn.net/hitwhylz/article/details/9492159?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-1-9492159-blog-140367622.235^v43^pc_blog_bottom_relevance_base6&spm=1001.2101.3001.4242.2&utm_relevant_index=4

案例：

1.递归函数求阶乘

#include<stdio.h>

long ff(int n)
{
long f;
if(n<0) printf("n<0,input error");
else if(n==0||n==1) f=1;
else f=ff(n-1)*n;
return(f);
}
int main()
{
int n;
long y;
scanf("%d",&n);
y=ff(n);
printf("%ld",y);
return 0;
}

解析：

f = ff(n - 1) * n;

这行代码是在计算阶乘时使用的递归公式。阶乘的定义是所有小于或等于该数的正整数的乘积。例如，5的阶乘（记作5!）是所有从1到5的整数的乘积，即：

5!=5×4×3×2×15!=5×4×3×2×1

现在，让我们用具体的数字来解释这行代码：

假设我们要计算5的阶乘，即ff(5)：

首先，我们调用ff(5)。
因为n不等于0或1，所以我们执行f = ff(n - 1) * n，即f = ff(5 - 1) * 5。
这就变成了f = ff(4) * 5。
我们继续这个过程，ff(4)会计算4!，即ff(4 - 1) * 4，也就是ff(3) * 4。
这个过程一直持续，直到我们到达基本情况，即n为0或1。对于ff(1)，我们知道1! = 1，所以ff(1)返回1。
然后，我们开始返回计算的结果。ff(2)会返回ff(1) * 2，也就是1 * 2 = 2。
ff(3)会返回ff(2) * 3，也就是2 * 3 = 6。
ff(4)会返回ff(3) * 4，也就是6 * 4 = 24。
最后，ff(5)会返回ff(4) * 5，也就是24 * 5 = 120。

所以，ff(5)的结果是120，这就是5的阶乘。这个过程展示了递归函数如何通过将问题分解成更小的问题（这里是计算n-1的阶乘）来解决问题，然后将这些小问题的解组合起来得到原始问题的解。

2.递归函数返回一段连续整数的和

#include <stdio.h>

// 直接递归方式实现
long sumRecursive1(int a, int b) {
if (a > b) {
return 0;
} else {
return a + sumRecursive1(a + 1, b);
}
}

int main() {
int m, n;
scanf("%d %d", &m, &n);
printf("%ld\n", sumRecursive1(m, n));
return 0;
}

这段代码是递归函数 sumRecursive1 的一部分，它用于计算从 a 到 b（包括 a 和 b）之间所有整数的和。让我们通过一个具体的例子来解释这段代码是如何工作的。

假设我们要计算从 a = 3 到 b = 5 之间所有整数的和，即求 3 + 4 + 5 的和。

递归过程

初始调用：我们首先调用 sumRecursive1(3, 5)。
第一次递归：因为 a = 3 不大于 b = 5，所以函数执行 return 3 + sumRecursive1(3 + 1, 5)，即 return 3 + sumRecursive1(4, 5)。
第二次递归：现在我们调用 sumRecursive1(4, 5)。同样，因为 a = 4 不大于 b = 5，所以函数执行 return 4 + sumRecursive1(4 + 1, 5)，即 return 4 + sumRecursive1(5, 5)。
基本情况：最后我们调用 sumRecursive1(5, 5)。这次，a = 5 等于 b = 5，所以函数不再递归，直接返回 5。
返回计算：从基本情况开始，我们逐步返回并计算总和：
- sumRecursive1(4, 5) 返回 4 + 5 = 9。
- sumRecursive1(3, 5) 返回 3 + 9 = 12。

所以，sumRecursive1(3, 5) 的最终结果是 12，这就是从 3 到 5 之间所有整数的和。

代码解释

return a + sumRecursive1(a + 1, b); 这行代码的意思是：当前递归调用返回 a 加上从 a + 1 到 b 之间所有整数的和。这是通过递归调用 sumRecursive1 函数实现的，每次递归调用都将 a 的值增加 1，直到 a 等于 b，这时递归结束。

这种递归方法直观地模拟了求和的过程，每一步都计算当前值 a 并将其加到下一次递归调用的结果上，直到达到结束条件。

3.斐波那契数列

#include <stdio.h>
// 递归方式实现Fibonacci数列
long long fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}

int main() {
int N;
scanf("%d", &N);
printf("%lld\n", fibonacci(N));
return 0;
}

这段代码是计算Fibonacci数列第N项的递归函数的核心部分。Fibonacci数列是一个著名的数列，其中每一项都是前两项的和，通常定义如下：

- 第0项（F(0)）是0
- 第1项（F(1)）是1
- 对于n >= 2，第n项（F(n)）是第(n-1)项和第(n-2)项的和，即 F(n) = F(n-1) + F(n-2)

现在，让我们逐步解释这段代码：

```c
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
```

1. **基本情况（Base Case）**:
- `if (n <= 1) { return n; }`
- 这部分是递归的基本情况。它检查是否达到了数列的开始部分，即第0项或第1项。
- 如果`n`是0或1，函数直接返回`n`，因为Fibonacci数列的第0项是0，第1项是1。

2. **递归步骤（Recursive Step）**:
- `else { return fibonacci(n - 1) + fibonacci(n - 2); }`
- 如果`n`大于1，函数进入递归步骤。
- 函数调用自身两次，一次计算第`n-1`项的值（`fibonacci(n - 1)`），另一次计算第`n-2`项的值（`fibonacci(n - 2)`）。
- 这两个调用的结果相加，得到第`n`项的值。

### 具体例子

让我们通过一个具体的例子来说明这个过程，假设我们要计算Fibonacci数列的第5项（F(5)）：

1. **初始调用**：`fibonacci(5)`
2. **第一次递归**：因为`5 > 1`，所以执行`fibonacci(5 - 1) + fibonacci(5 - 2)`，即`fibonacci(4) + fibonacci(3)`。
3. **第二次递归**：
- `fibonacci(4)`进一步分解为`fibonacci(3) + fibonacci(2)`。
- `fibonacci(3)`进一步分解为`fibonacci(2) + fibonacci(1)`。
4. **基本情况**：
- `fibonacci(2)`返回2（因为`2 <= 1`不成立，继续分解）。
- `fibonacci(1)`返回1（基本情况）。
- `fibonacci(0)`返回0（基本情况）。
5. **返回计算**：
- `fibonacci(3)`返回`fibonacci(2) + fibonacci(1) = 2 + 1 = 3`。
- `fibonacci(4)`返回`fibonacci(3) + fibonacci(2) = 3 + 2 = 5`。
- 最终，`fibonacci(5)`返回`fibonacci(4) + fibonacci(3) = 5 + 3 = 8`。

因此，Fibonacci数列的第5项是8。这个过程展示了递归函数如何通过将问题分解成更小的问题来解决问题，然后将这些小问题的解组合起来得到原始问题的解。

4.求两个数的最大公约数

#include <stdio.h>

// 递归方式实现计算最大公约数
int gcd(int a, int b) {
if (b == 0) {
return a; // 递归的基本情况，当b为0时，a就是最大公约数
} else {
return gcd(b, a % b); // 递归调用，计算b和a除以b的余数的最大公约数
}
}

int main() {
int m, n;
scanf("%d %d", &m, &n); // 输入两个整数
printf("%d\n", gcd(m, n)); // 输出最大公约数
return 0;
}

`return gcd(b, a % b)` 这行代码是欧几里得算法的核心，用于递归地计算两个正整数 `a` 和 `b` 的最大公约数（GCD）。让我们逐步解释这行代码的含义和工作原理。

### 欧几里得算法的基本原理

欧几里得算法基于这样一个事实：两个整数 `a` 和 `b`（假设 `a > b`）的最大公约数与 `b` 和 `a` 除以 `b` 的余数 `r`（即 `a % b`）的最大公约数相同。数学上可以表示为：

\[ \text{GCD}(a, b) = \text{GCD}(b, a \mod b) \]

### 代码解释

- `return gcd(b, a % b)`：这行代码表示函数调用自身（递归调用），但参数交换了位置，并且第二个参数变成了 `a` 除以 `b` 的余数。

### 具体例子

让我们通过一个具体的例子来说明这个过程，假设我们要计算 `a = 48` 和 `b = 18` 的最大公约数：

1. **初始调用**：`gcd(48, 18)`
2. **第一次递归**：
- 计算 `48 % 18`，得到余数 `12`。
- 调用 `gcd(18, 12)`。
3. **第二次递归**：
- 计算 `18 % 12`，得到余数 `6`。
- 调用 `gcd(12, 6)`。
4. **第三次递归**：
- 计算 `12 % 6`，得到余数 `0`。
- 调用 `gcd(6, 0)`。
5. **基本情况**：
- 当 `b` 变为 `0` 时，递归结束，`a`（此时为 `6`）就是最大公约数。
6. **返回计算**：
- `gcd(6, 0)` 返回 `6`。
- `gcd(12, 6)` 返回 `6`。
- `gcd(18, 12)` 返回 `6`。
- 最终，`gcd(48, 18)` 返回 `6`。

因此，`48` 和 `18` 的最大公约数是 `6`。

### 总结

`return gcd(b, a % b)` 这行代码通过递归的方式，不断地将问题规模缩小，直到达到基本情况（当 `b` 为 `0` 时），然后逐层返回，最终得到原始问题的解。这种方法有效地利用了数学上的等价关系，将问题分解为更小的子问题，直到可以直接解决为止。

5.递归函数输出一个十进制整数的二进制形式

#include<stdio.h>
void dectobin(int n)
{
if (n == 0)
return;
else
{
dectobin(n / 2);
printf("%d", n % 2);
}

}
int main()
{
int n,a;
scanf("%d%d",&n,&a);
for (int i = n; i <= a; ++i) {
dectobin(i);
printf("\n");
}
return 0;
}

这个程序中使用的递归方法来将十进制数转换成二进制的思路基于二进制的除以2取余法。下面详细解释这个方法：

思路解释

基本思想：二进制是一种基数为2的数制，每一位上的数字只能是0或1。将十进制数转换成二进制的过程，实际上是不断地将这个数除以2，并记录下每次除法的余数。余数就是当前位的二进制位。
递归实现：
- 递归调用：首先，将n除以2，得到商和余数。递归调用dectobin(n / 2)，处理商，即处理n的高位部分。
- 打印余数：在递归调用返回后，打印出n % 2的结果，即n的最低位（0或1）。
递归终止：当n减到0时，递归终止。这是因为0的二进制表示就是0。

方法推广

这种方法不仅可以用于将十进制数转换为二进制，还可以推广到其他进制的转换。例如，将十进制数转换为八进制（基数8）或十六进制（基数16）：

八进制转换：每次除以8，记录余数。
十六进制转换：每次除以16，记录余数。

对于八进制和十六进制，由于余数可能大于9，需要将余数转换为对应的字符（A-F）来表示。

6.递归函数输出一个十进制整数的十六进制形式

#include <stdio.h>

void fun(int a, int b){

printf("%X", a); //printf函数可以直接以16进制的形式来输出
//%d十进制，%o八进制，%X大写16进制，%x小写16进制
if(a == b) return ;

printf(" "); //最后a==b时不需要输出后面的空格

fun(a+1, b);
}

int main(){

int a, b;
scanf("%d %d", &a, &b);

fun(a, b);

return 0;
}

7.逆序输出整数

#include<stdio.h>
void print(int n)//递归函数，取余
{
if(n==0) return;
else{
printf("%d",n%10);//取余并输出
print(n/10);//递归调用，实现逆序输出
return;
}
}
int main()
{
long n;//题目要求整型就好int也OK
scanf("%d",&n);
print(n);//调用递归函数
return 0;
}

标签：return,语言,递归,int,sumRecursive1,fibonacci,ff,递推
From： https://www.cnblogs.com/0329cc/p/18617912

递归过程

代码解释

思路解释

方法推广

相关文章

赞助商

阅读排行

c语言 递归 递推

递归过程

代码解释

思路解释

方法推广

相关文章

赞助商

阅读排行

c语言递归递推