Regressive Recursion

This Demonstration shows a definition by regressive recursion. The domain of the functions considered is the set of non-negative integers. Given an increasing function , define the predicate . Two other functions and are also given. The new function is defined by: if , then ; otherwise, .


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


If , and are primitive recursive functions, is also a primitive recursive function [1].
[1] I. Hafner, "Regressive Recursion," Mathematica Balkanica, 6(13), 1976 pp. 75–77.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.