Background

Description

一、递归和递推的区别

递归和递推都是计算机程序设计中常用的算法思想，它们有以下的区别：

1、实现方式不同

递归是通过函数的自我调用来实现的，而递推则是通过循环来实现的。

2、运行效率不同

递归可能会导致函数调用的层级过深，从而导致栈溢出等问题。而递推则可以避免这个问题，运行效率通常比递归高。

3、代码可读性不同

递归的代码比较简洁易懂，但可能会难以理解和调试。而递推的代码比较冗长，但结构清晰，易于理解和调试。

4、适用范围不同

递归通常适用于解决递归性质的问题，例如二叉树的遍历、图的深度优先搜索等。而递推通常适用于解决数学归纳的问题，例如斐波那契数列、阶乘等。

因此，在选择使用递归还是递推时，需要考虑算法的复杂度、可读性和实际问题的特点，选择非常适合的算法实现。

Format

Input

Output

Samples

Limitation

1s, 1024KiB for each test case.