Question

用递归解决的问题一般不需要具备哪些特点

Answer 1

问：用递归解决的问题一般不需要具备哪些特点

答：递归解决的问题一般不需要具备以下特点:1. 重复计算:递归会导致相同的计算被重复进行多次,所以递归不适合需要大量重复计算的问题。2. 过大的输入:递归涉及函数调用自身,如果输入过大,递归层级会太深,很容易导致栈溢出。所以递归不适合处理过大输入的问题。3. 循环迭代:递归适合解决可以分解为互相调用的子问题的问题,不太适合循环迭代的问题。循环迭代的问题一般用迭代来解决更合适。4. 共享状态:递归函数在每次调用时会创建一个新的栈帧,不会共享状态。所以递归不适合需要共享和更新状态的问题。

问：你讲得真棒！可否详细说一下

答：总之,递归更适合解决可以分解为相互调用的子问题,而且子问题规模越来越小的问题。如果一个问题涉及大量重复计算、过大输入、循环迭代以及需要共享的状态,那么递归可能就不太适合,可以考虑用迭代来解决。递归主要利用函数栈来保存状态和递归层级,每次函数调用时创建一个新的栈帧。所以递归函数调用的次数不能太多,否则很容易栈溢出。而迭代利用程序循环和变量来维护状态,没有函数调用,所以不会有栈溢出的问题,可以处理更大规模的输入。