我试图理解下面的 C 代码是如何工作的:
int factorial(int n) {
int result;
if(n==0){
result=1;
}else{
result = n * factorial(n-1);
}
return result;
}
我知道输出是 n 的阶乘。我想我想了解这个递归示例是否使用 if 语句作为递归的原因。是否也可以使用 for 循环而不是 if 来执行递归?还是我完全错过了重点?
最佳答案
I guess Im trying to understand if this example of recursion is using the if statement as the cause for recursion.
递归的原因是函数调用自身。 if (n == 0)
条件告诉我们何时停止递归。
如果我们调用 factorial(3)
,递归看起来像这样:
factorial(3):
return 3 * factorial(2): -----------+
return 2 * factorial(1); ------+ |
return 1 * factorial(0); --+ | |
return 1; | | |
1; <-----------------------+ | |
2; <---------------------------+ |
6; <--------------------------------+
And can recursion for this also be performed with a for loop instead of the if?
在这种情况下您不会使用循环 - 递归本身就是一种循环。
对于计算阶乘、斐波那契数等,我认为迭代算法(循环)优于递归算法:
int factorial_iter( int n )
{
int result = 1;
while ( n )
result *= n--;
return result;
}
因为与进行 n
单独的函数调用相比,开销非常小。但是,使用递归定义,阶乘更容易表达:
n! = n * n-1!, 0! = 1
所以你经常看到它被用作编程中递归的例子。事实上,像 Haskell 这样的语言几乎遵循数学符号:
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial( n - 1 )
任何可以递归解决的问题都可以迭代解决,尽管有些解决方案(快速排序、树遍历等)更容易递归实现。
例如,一个中序树的遍历可以写成
/**
* Perform an inorder traversal by
* visiting the left subtree, then the root,
* then the right subtree.
*/
void inorder( node_type *t )
{
if ( !t )
return;
inorder( t->left );
do_something_with( t->data );
inorder( t->right );
}
这比尝试编写一个循环以正确的顺序访问所有节点要简单得多。
关于c - 试图理解 C 中的递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53714480/