我知道递归有时比循环要简洁得多,我不是在问什么时候应该用递归而不是迭代,我知道已经有很多关于这个的问题了。
我问的是,递归比循环快吗?在我看来,你总是能够细化一个循环,让它比递归函数执行得更快,因为循环是不存在的,不断地建立新的堆栈帧。
我特别在寻找在递归是正确处理数据的方法的应用程序中递归是否更快,例如在一些排序函数中,在二叉树中等等。
我知道递归有时比循环要简洁得多,我不是在问什么时候应该用递归而不是迭代,我知道已经有很多关于这个的问题了。
我问的是,递归比循环快吗?在我看来,你总是能够细化一个循环,让它比递归函数执行得更快,因为循环是不存在的,不断地建立新的堆栈帧。
我特别在寻找在递归是正确处理数据的方法的应用程序中递归是否更快,例如在一些排序函数中,在二叉树中等等。
当前回答
递归在显式管理堆栈的情况下可能更快,就像你提到的排序或二叉树算法一样。
我曾经遇到过这样的情况,用Java重写递归算法会让它变慢。
因此,正确的方法是首先以最自然的方式编写它,只在分析显示它至关重要时进行优化,然后衡量假定的改进。
其他回答
在任何现实的系统中,不,创建一个堆栈框架总是比创建INC和JMP更昂贵。这就是为什么真正好的编译器会自动将尾递归转换为对同一帧的调用,也就是说,没有开销,所以你会得到更可读的源版本和更有效的编译版本。一个非常非常好的编译器甚至应该能够在可能的情况下将普通的递归转换为尾部递归。
尾递归和循环一样快。许多函数式语言都实现了尾部递归。
递归在显式管理堆栈的情况下可能更快,就像你提到的排序或二叉树算法一样。
我曾经遇到过这样的情况,用Java重写递归算法会让它变慢。
因此,正确的方法是首先以最自然的方式编写它,只在分析显示它至关重要时进行优化,然后衡量假定的改进。
这只是猜测。一般来说,如果两者都使用了非常好的算法(不考虑实现难度),那么在规模相当大的问题上,递归可能不会经常击败循环,如果使用带有尾部调用递归的语言(以及带有循环的尾部递归算法,也是语言的一部分),情况可能会有所不同——它们可能非常相似,甚至有时更喜欢递归。
考虑每个迭代和递归都必须做什么。
迭代:跳转到循环的开始 递归:跳转到被调用函数的开头
你看,这里没有多少分歧的余地。
(我假设递归是尾部调用,编译器知道这种优化)。