我不明白这两个变量是如何成比例的

Question

计算机程序的结构和解释第 1.2.1 节线性递归和迭代：

Compare the two processes... each requires a number of steps proportional to n to compute n!

两个进程由

指定

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

;; This is the linear recursive process

(define (factorial n)
 (define (iter product counter)
   (if (> counter n)
       product
       (iter (* counter product)
             (+ counter 1))))
 (iter 1 1))

;; This is the linear iterative process

我的问题是：这两个过程如何需要与 n 成正比的步数来计算 n！？

Answer 1

对于第一个过程；您必须在一个递归循环中执行这些步骤：

- check if n equals 1
- multiply n with (factorial (- n 1))
  if we split it a little, it includes (- n 1) and a function call and a multiplication.

我们粗略地算作 4 个步骤。

而且因为你必须做这4个步骤直到n = 1，所以总共是4*n个步骤。所以它与n成正比。（我们忽略一些细节，例如，n=1 情况的处理有点不同，因为当 n 足够大时，可以忽略）

第二个一样

Answer 2

在这两种情况下，程序将保持运行，直到满足特定条件。

递归过程将继续调用 (factorial) 过程并递减 n 直到 n=1
迭代过程将不断增加 counter 变量，直到 counter > n

n 的值越大，满足每次终止检查所需的时间就越长。

示例： (factorial 1000) 将比 (factorial 10) 花费更长的时间，因为从 1000 到 1 需要 999 步，每次将 n 减 1 time factorial 被调用（在递归过程中）。另一方面，10 比 1 只需 9 步。

希望这能回答您的问题。

我不明白这两个变量是如何成比例的

I don't understand how these two variables are proportionate

sicp