19

为了理解贪婪方法和动态规划等高级算法概念，首先需要精通递归。

我对递归比较陌生。每当提出问题时，首先想到的就是使用迭代的解决方案。尽管我知道递归方法的含义以及它是如何工作的，但很难以递归的方式思考。

请通过回答以下问题来提供帮助：

1）任何迭代方法都可以用递归代替吗？反之亦然？

例如，如何递归地打印大小为 n 的数组中的元素？

for i 0 to n
 Print a[i]

2）如何递归解决问题？步骤是什么？是否有任何提示可以确定可以递归解决问题？

例如：如果要求打印出字符串的所有子字符串

INPUT: CAT
OUTPUT: CAT,CA,A,AT,T

我可以快速想出一种迭代方式。使用两个循环可以解决问题。

但是如何递归地解决它。如何确定一个问题可以递归地解决。

如果我的第一个问题的答案是肯定的，那么使用两个递归而不是迭代可以解决我的问题吗？

3）谁能建议我一些材料/资源来彻底理解递归的概念？

4

8 回答 8

24

有一种思考递归的方法，使它像迭代一样简单。

在迭代中，我们有一个循环。认为它有 4 个部分：

  1. 基于一些“控制”数据的继续或停止的决定，被评估为逻辑条件。

  2. 一个身体，工作完成的地方。有时，身体与下一部分结合在一起。

  3. 一种更改“控制”数据的方法。通常通过更换计数器。

  4. 再次调用构造（在本例中为循环）的一种方式。在 c 风格的语言中，这是由 for、while 或 do 语法提供的。

在递归中，我们有一个函数（有时是几个）。它们具有相同的 4 个部分：

  1. 基于一些“控制”数据的继续或停止的决定，被评估为逻辑条件。控制数据通常作为参数传递给函数。

  2. 一个身体，工作完成的地方。有时，身体与下一部分结合在一起。

  3. 一种更改“控制”数据的方法。通常通过更换计数器。

  4. 再次调用构造（在本例中为函数）的一种方式 - 这意味着调用函数（并记住传递更改的“控制”数据。

这两个结构具有相同的部分也就不足为奇了，因为它们是等价的。

于 2013-07-12T11:35:34.270 回答
9

  1. 是的，主要是。一般来说，递归是为程序员而不是计算机而完成的。有一些迭代方法在某些情况下可能比递归方法运行得更快，但是迭代方法可能需要 300 行代码和递归 3 行。还有一些情况很容易弄清楚如何递归地编程，但是非常难以迭代编写，反之亦然。

  2. 通常，递归解决方案需要根据功能进行。如果我们使用像 C++ 这样的东西，我们可以使用处理字符串引用和事物的解决方案，慢慢调整作为参数传递的字符串。但是，“两次递归”结束附近的点被误导了。这里的原则是，我们可以做一种递归方法，而不是两次迭代。

  3. http://introcs.cs.princeton.edu/java/23recursion/这个网站（在谷歌搜索上排名靠前）教授了很多递归的数学理论，并包含一个常见问题解答，它可能会给你一个更令人满意的答案.

于 2013-07-12T09:13:43.317 回答
8

让我们做一个简单的任务。打印从 1 到 10 的数字。我将在这里使用 Python2.7。

for i in range(1,11):
    print i

现在让我们尝试做同样的事情，使用递归。

>>> def print_me(n):
    if n > 0:
        print_me(n - 1)
        print n
    else:
        return

>>> print_me(10)
1
2
3
4
5
6
7
8
9
10

那么我们怎么看呢？

  • Step1：想想我的界限。我需要两个。1 和 10。接下来。
  • Step2：打印语句。这就是我们的动机。打印数字。我们希望它从 1 到 10。所以我需要先打印 1。

  • 第三步：我们首先编写一个函数来打印作为参数传递的数字。让我们想想，主要任务。

    def print_me(n): 打印 n

  • 第 4 步：如果 n < 1，我希望函数返回。

    def print_me(n): if n > 0: print n else: return

  • 第 5 步：现在我想将 1 到 10 的数字传递给这个函数，但我们不想要 1 到 10 的循环，然后将它传递给我们的函数。我们希望它以递归方式完成。

什么是递归？ 简而言之，递归过程或定义的重复应用。

所以为了让它递归，我们需要调用函数本身。我们想通过我们的 1 到 10 的范围。

def print_me(n):
    if n > 0:
        print_me(n - 1)
        print n
    else:
        return

总结：所有递归调用必须遵守 3 个重要规则：

  1. 递归算法，必须有一个基本情况。
  2. 递归算法，必须改变它的状态并朝着基本情况移动。
  3. 递归算法必须以递归方式调用自身。

来源：交互式python

另一个在 Javascript 中查找阶乘的程序：

function factorial(n){
    if (n == 1)
        {
        return 1;
        }
    else {
        return n * factorial(n-1);
        }
}
于 2017-02-14T07:52:13.333 回答
1 
@Test
public void testStrings() {
   TreeSet<String> finalTree = getSubStringsOf("STACK");
    for(String subString : finalTree){
        System.out.println(subString);
    }
}

public TreeSet<String> getSubStringsOf(String stringIn) {
    TreeSet<String> stringOut = new TreeSet<String>();
    if (stringIn.length() == 1) {
        stringOut.add(stringIn);
        return stringOut;
    } else {
        for (int i = 1; i < stringIn.length() ; i++) {
            String stringBefore = stringIn.substring(0, i);
            String stringAfter = stringIn.substring(i);
            stringOut.add(stringBefore);
            stringOut.add(stringAfter);
            stringOut.addAll(getSubStringsOf(stringBefore));
            stringOut.addAll(getSubStringsOf(stringAfter));
        }
        return stringOut;
    }
}

我不知道你是否需要解释。每次可能时，您都将字符串分成两部分。因此，Cat 分为 CA,T 和 C,AT，您将它们添加到子字符串列表中，然后查找这些子字符串的每个子字符串。如果字符串是单个字符，则将单个字符添加到树中。

编辑：这是堆栈的输出：

A AC ACK C CK K S ST STA STAC T TA TAC TACK

再次编辑：如您所见，每次运行 subString 方法时，都会在其中使用两次，除非它是单个字符串。因此复杂度为 O(n²)。对于“STACK”，程序长 0.200 毫秒，“STACKSTACKSTACK”（3 次堆栈）为 2 秒，“STACKSTACKSTACKSTACKSTACK”理论上是 2^10 倍，因此为 2000 秒。

于 2013-07-12T09:49:02.047 回答
1

这是在 C++ 中递归打印数组的代码

#include<iostream>
using namespace std;

void print(int arr[],int n)
{
if(n==0)     //base case. function call hits the base case when n==0
{
cout<<arr[0]<<" ";
return;
}
print(arr,n-1);   //function will be called recursively until it reaches the 
                    base case.
cout<<arr[n]<<" ";
}
              //Driver function
int main()
{
int arr[]={10,20,30,40,50}; //array has been initialized with values 
                                               // 10,20,30,40,50 

int n=sizeof(arr)/sizeof(arr[0]) ; //n stores the size of array,i.e, n=5; 
print(arr,n-1);   //print function has been called with arr[] and (n-1) as 
                    parameters.
return 0;
}

我希望它以某种方式有所帮助

于 2020-11-05T15:05:45.217 回答
1

CAT问题可以这样解决：（Python代码）

s = "CAT"
op = []
def sub(s):
    # terminating condition.
    if (len(s) == 0) : return

    if s not in op : op.append(s)
    
    # slices from begning
    sub(s[1:])
    # slices from the end
    sub(s[:-1])

sub(s)
print(op)

Output : ['CAT', 'AT', 'T', 'A', 'CA', 'C']
于 2020-11-13T14:37:52.930 回答
1

这是我在 Python 中的简单测试：

def p(l, index):
    if index == len(l):
        return
    else:
        print l[index]
        index = index + 1
        p(l, index)

并致电：

p("123456", 0)
于 2018-01-19T03:25:07.273 回答
1

我认为我们可以使用递归函数解决任何迭代问题，但它可能不是最有效的方法。这是一个在 Python3 中同时使用“for 循环”和“递归”打印列表中项目的简单示例：

a = [ 1,2,3,4,5] 
#iterative approach using a for loop
for i in nums:
   print(i)

#recursive approach
def printing_list(nums):
    #base case
    if len(nums)==0:
        return
    #recursive
    else:
        print(nums[0])
    return printing_list(nums[1:])

printing_list(nums)

要递归思考，最好先编写 for 循环，然后尝试在此基础上编写递归解决方案。记住所有递归方法都需要一个基本案例来停止递归

于 2021-11-09T17:54:20.510 回答