东北大学2024年冬计算机组成_问题5

东北大学2024年冬计算机_问题5 by 偷偷

催更｜辅导｜私塾兼职｜联系偷偷：LifeGoesOn_Rio

Consider the following recursive function $f$ that takes an integer and returns an integer.

$$
f(n)=
\begin{cases}
0,\quad n\leq 0 \\
f(n-1) \times 2 + n, \quad n>0
\end{cases}
$$

Answer the following questions.

---

(1) Find the value of $f(3)$. Show also the intermediate steps in the calculation.

$$f(0) = 0$$
$$f(1) = f(0) \times 2 + 1 = 1$$
$$f(2) = f(1) \times 2 + 2 = 4$$
$$f(3) = f(2) \times 2 + 3 = 11$$

---

(2) Consider a machine with three integer registers $r_{0}$, $r_{1}$, and $r_{2}$, a stack of sufficient size, and the instruction set in Fig.5(a). A program is a sequence of instructions and there is no limit on the size of integers. The program in Fig.5(b) displays the value of $f(30)$ on the screen and terminates. Give an instruction (or part of an instruction) that is appropriate for each of (A), (B), (C), and (D). Also explains in several lines of text how this program goes.

Let’s briefly read the assembly language

1. set 30, $r1
2. set 5, $r0      # 这里的‘5’用来记录函数退出的位置，即第5行代码
3. push r0
4. jmp 6
5. halt r1         # r1用来返回最终的计算结果
6. ifpos r1, ______(A) # 循环
7. set 0, r1
8. ret
9. push r1              # 不断往栈放入r1，后续必定有弹出r1的动作
10. dec r1
11. set ____(B), r0
12. push r0
13. jmp 6              # 循环
14. add r1, r1, r2     # 计算乘2的过程，即f(n-1) x 2
15. ____(C)
16. add r1, r2, r1     # 计算加n的过程
17. ____(D)            # 需要找准时机退出循环，即要和‘5’呼应上

Hint: 可以尝试令$r1 = 3, 然后手动模拟栈计算f(3)的过程

Ans:

• (A): jmp 9
• (B): 14
• (C): pop r1
• (D): ret

This program initially places the calculation of the recursive endpoint $f(30)$ at the bottom of the stack. It then recursively processes from the bottom upwards until the starting value of the recursion is placed at the top of the stack. Following this, it begins to recursively process from the top downward until it reaches the calculation of the recursive endpoint $f(30)$.