計算機科学のブログ

Building Abstractions with Functions - The Elements of Programming - Linear Recursion and Iteration - substitution model

Structure and Interpretation of Computer Programs: JavaScript Edition(Harold Abelson(著)、Gerald Jay Sussman(著)、Julie Sussman(著)、The MIT Press)のChapter 1(Building Abstractions with Functions)、1.1(The Elements of Programming)、1.2.1(Linear Recursion and Iteration)、Exercise 1.9の解答を求めてみる。

1つ目の関数の場合。

  • plus(4, 5)
  • 4 === 0 ? 5 : inc(plus(dec(4), 5))
  • inc(plus(dec(4), 5))
  • inc(plus(3, 5))
  • inc(3 === 0 ? 5 : inc(plus(dec(3), 5)))
  • inc(inc(plus(dec(3), 5)))
  • inc(inc(plus(2, 5)))
  • inc(inc(2 === 0 ? 5 : inc(plus(dec(2), 5))))
  • inc(inc(inc(plus(dec(2), 5))))
  • inc(inc(inc(plus(1, 5))))
  • inc(inc(inc(1 === 0 ? 5 : inc(plus(dec(1), 5)))))
  • inc(inc(inc(inc(plus(0, 5)))))
  • inc(inc(inc(inc(0 === 0 ? 5 : inc(plus(dec(0), 5))))))
  • inc(inc(inc(inc(5))))
  • inc(inc(inc(6)))
  • inc(inc(7))
  • inc(8)
  • 9

2つ目の関数の場合。

  • plus(4, 5)
  • 4 === 0 ? 5 : plus(dec(4), inc(5))
  • plus(dec(4), inc(5))
  • plus(3, 6)
  • 3 === 0 ? 6 : plus(dec(3), inc(6))
  • plus(dec(3), inc(6))
  • plus(2, 7)
  • 2 === 0 ? 7 : plus(dec(2), inc(7))
  • plus(dec(2), inc(7))
  • plus(1, 8)
  • 1 === 0 ? 7 : plus(dec(1), inc(8))
  • plus(dec(1), inc(8))
  • plus(0, 9)
  • 0 === 0 ? 9 : plus(dec(0), inc(9))
  • 9

processesについて、1つ目の関数がrecursiveで2つ目の関数がiterative。