recursion - “单程”一词是如何定义的？

Question

一次执行过程是否意味着非递归？或者这是否意味着该过程不应该在相同的信息上重复两次？

我问这个是因为我的印象是它是第一个定义，但现在我偶然发现了一个作业问题，如果不使用递归我无法弄清楚，但说“一次性完成”。

Answer 1

单遍是指您仅在集合中迭代一次（仅触摸每个元素一次）。

您可以通过像这样的简单迭代来完成此操作

for n from 0 to set length
 interact with set item n

或者你可以递归（c#）

public int total(int[] numbers,int index)
    {
     if (index == numbers.Length - 1) return numbers[index];
     return numbers[index] + total(numbers, index + 1);
    }

int[] someInts = {1,2,3,4};
int intTotal = total(someInts,0);

Answer 2

“单程”意味着访问元素集合中的每个元素（例如：列表、数组、集合、向量、映射、树、图、字符串等）（“迭代over") 一次且仅一次 - 过程是递归的还是迭代的都没有关系。例如，Scheme 中的以下递归过程一次添加列表中的所有元素：

(define (sum lst)
  (if (null? lst)
      0
      (+ (car lst)
         (sum (cdr lst)))))

相同的过程可以用尾递归方式编写 - 意思是：当递归调用发生在另一个过程中时，是它的最终动作；它可能会产生一个返回值，然后由调用过程立即返回。无论如何，只对列表中的元素执行一次传递：

(define (sum lst)
  (let loop ((lst lst)
             (acc   0))
    (if (null? lst)
        acc
        (loop (cdr lst) (+ (car lst) acc)))))

将上面的两个示例与 Java 中的这段代码进行比较：它是一个迭代方法，但再次对数组执行单遍：

int sum(int[] array) {
    int acc = 0;
    for (int x : array)
        acc += x;
    return acc;
}