时间戳

首页 > 解决方案 > 我不明白这两个变量是如何成比例的

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

问题描述

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

比较这两个过程......每个过程都需要与 n 成比例的步骤来计算 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！?

标签： sicp

解决方案

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

- 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 足够大时，可以忽略）

第二个是一样的

推荐阅读