可视化递归扩缩容的过程

Question

我正在练习 SICP 的练习 1.17

#+begin_src ipython :session alinbx :results output
def fast_mul(a, b):
    if b == 1: return a
    else:
        if even(b): return 2 * fast_mul(a, b//2)
        if odd(b):  return a  + 2 * fast_mul(a, b//2)
def even(n):
    return n % 2 == 0

def odd(n):
    return n % 2 == 1
print(fast_mul(3, 7))
#+end_src

#+RESULTS:
: 21

加print为

怎么能看出扩缩的过程

fast_mul(3,7)
3 + 2 * fast_mul(3, 3)
3 + 2 * (3 + 2 * fast_mul(3, 1))
3 + 2 * (3 + 2 * 3)
21

Answer 1

def fast_mul(a, b, s, d):
    if b == 1:
        print(s,a,') '*d)
        return a
    else:
        if even(b):
            print(s+f'2 * fast_mul({a}, {b//2})',') '*d)
            return 2 * fast_mul(a, b//2, s+'2 * ( ',d+1)
        if odd(b):
            print(s+f'{a} + 2 * fast_mul({a}, {b//2})', ') '*d)
            return a  + 2 * fast_mul(a, b//2,s+f'{a} + 2 * ( ',d+1)
def even(n):
    return n % 2 == 0

def odd(n):
    return n % 2 == 1
print(fast_mul(3, 7,'',0))

我在函数中添加了两个参数，s 和 d。

s 存储从上一个递归调用中结转的字符串

d 存储递归的深度，因此我们可以计算出要添加到字符串中的右括号的数量。

Answer 2

听起来您正在寻找 trace，尽管默认设置可能需要一些技巧才能 return 您正在寻找的具体细节，例如

python -m trace -t fast_mul.py

在 elisp 中，默认跟踪更接近您想要的输出，例如。

(defun fast-mul (a b)
  (if (eq 1 b) a
    (+ (if (evenp b) 0 a) (* 2 (fast-mul a (/ b 2))))))

(trace-function 'fast-mul)
(fast-mul 3 7)

;; 1 -> (fast-mul 3 7)
;; | 2 -> (fast-mul 3 3)
;; | | 3 -> (fast-mul 3 1)
;; | | 3 <- fast-mul: 3
;; | 2 <- fast-mul: 9
;; 1 <- fast-mul: 21

可视化递归扩缩容的过程

Visualize the process of expand and contraction of recursion

sicp

python-3.x