;; This program reads in a number n, computes f(n), and writes it out.
;; The function f is defined as follows.
;;   f(0) = 1
;;   f(n) = 2f(n-1) + n for n > 0
;;
;; Date Written: 2008/02/18
;; Author: SS

  allocate-registers f, n, base-case, result, sp, one, cont

  li f Lf
  li base-case Lbase-case
  li sp 0
  li one 1

  read n
  li cont Lhere
  j f
Lhere:
  write result
  halt

;; This procedure computes f recursively.
;;
;; preconditions:
;;   input in register n
;;   return address in register cont
;; postcondition:
;;   register result contains f(n) such that
;;    f(0) = 1 and f(n) = 2f(n-1) + n if n > 0.

Lf:
  jeqz n base-case

;; save my context
  st n sp
  add sp sp one
  st cont sp
  add sp sp one

;; put the correct values in cont & n, then call f(n-1)
  li cont Lback
  sub n n one
  j f

Lback:
;; retrieve my context
  sub sp sp one
  ld cont sp
  sub sp sp one
  ld n sp

;; puts the value of 2 f(n-1) + n in result and return
  add result result result
  add result result n
  j cont

Lbase-case:
  li result 1
  j cont