python-3.x - 可视化递归的展开和收缩过程(Visualize the process of expand and contraction of recursion)

Question

I am practicing Exercise 1.17 of SICP

(我正在练习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

How could I see the process of expanding and contraction by adding print as

(我怎么能看到扩张和收缩的过程中加入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

  ask by Algebra translate from so

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))

I added two more parameters in the function, s and d.

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

s stores the string that's carried over from the previous recursion call

(s存储从上一个递归调用中继承的字符串)

d stores the depth of recursion so we can figure out how many closing brackets to add to the string.

(d存储递归的深度，因此我们可以算出要在字符串中添加多少个右括号。)