从零开始学习C++之递归

标签：return 递归 -- 元素 C++ int 从零开始 阶乘

递归

注：此算法与 函数 有关，如不了解请移步。

在 wiki pedia 中，递归的解释是这样的：

在 C++ 中，递归就是指在函数中调用函数本身；递归的作用类似于分治，将一个大问题分解为很多小问题进行求解。

但是递归的时间复杂度极高，因为要解决很多小问题，所以时间复杂度高达 \(O(2^n)\)。

使用

递归必须要有一个出口！！！（你肯定不想要死循环，对吧？）

这个出口就是我们停止递归的条件，将问题解决了/分解到可以直接解决的程度了就推出递归。、

例题

例题 1

求 \(n!\)，即 \(n\) 的阶乘。

流程图如下：

graph TD; A[求 $n$ 的阶乘] --> B[$n$ 是否等于 $1$？]; B[$n$ 是否等于 $1$？] --> |true| C[返回 $1$]; B[$n$ 是否等于 $1$？] --> |false| D[返回 $n \times$ $n - 1$的阶乘]; D[返回 $n \times$ $n - 1$的阶乘] --> |求 n - 1的阶乘| A[求 $n$ 的阶乘];

代码为：

int f(int n)
{
	if (n == 1)
		return 1;
	return n * f(n - 1);
}

例题 2

现在有一个斐波那契数列，求第 \(n\) 个元素。

graph TD; A[求第 $n$ 个元素] --> B[$n$ 是否等于 $1$ 或 $2$？]; B[$n$ 是否等于 $1$ 或 $2$？] --> |true| C[返回 $1$]; B[$n$ 是否等于 $1$ 或 $2$？] --> |false| D[返回 元素$n - 1$ $+$ 元素$n - 2$]; D[返回 元素$n - 1$ $+$ 元素$n - 2$] --> |求第 $n - 1$，$n - 2$ 个元素| A[求第 $n$ 个元素];

int f(int n)
{
	if (n == 1 || n == 2)
		return 1;
	return f(n - 1) + f(n - 2);
}

作者的话

作业：洛谷P1464

拜拜~

标签：return,递归,--,元素,C++,int,从零开始,阶乘
From： https://www.cnblogs.com/George222/p/18382883