The blanks are x < 2 and return x - foo(x + 1). The compiled slti and bne select the first branch exactly for . Otherwise addi forms , jal foo returns its value in $v0, and sub $v0, $s0, $v0 subtracts that value from the preserved . Thus the complete high-level implementation is
proc bar(val x : int) : int
begin if x < 2 then
          return 1
      else
          return x - foo(x + 1)
      end
end
Although the immediate call increases the argument, substitution into foo's two recursive calls decreases the corresponding bar arguments to and whenever the recursive branch is entered. The mutual recursion therefore terminates on ordinary integer inputs, assuming sufficient stack space and no machine arithmetic overflow.

Ancestors (11)

  1. 3
  2. Digital systems, linear algebra, introduction to formal proof
  3. 2016
  4. Past exam of the year 1 of the computer science course of the University of Oxford
  5. Year 1 of the computer science course of the University of Oxford
  6. Computer science course of the University of Oxford
  7. Undergraduate course of the University of Oxford
  8. Course of the University of Oxford
  9. University of Oxford
  10. List of universities
  11. Home

View article source

Discussion (0) New discussion

There are no discussions about this article yet.

Articles by others on the same topic (0)

There are currently no matching articles.
See all articles in the same topic Create my own version