/* recursion.c: Implement recursive/primitive recursive functions in C
This file declares a number of functions that build up to the
world's slowest implementation of the power function (x^y). The main
program is just a simple test platform for the power function. If
you wish, you could build other recursive functions and a different
test platform once you understand the pattern set out below.
compile: cc -o recursion -DPROFILE recursion.c
You could leave off -DPROFILE, but that includes variables that track
how many times each building block routine is called. You can then
have your main platform report these values. Otherwise, you just have
a very slow implementation of simple arithmetic functions.
*/
/* By Terry R. McConnell */
#include
#include
/*
The idea is that, after defining the base functions and rules, the
code for the remaining functions represents the proof that they are
primitive recursive (recursive).
A reference to the theory of recursive functions, which uses the notation
we use below, is "Introduction to Mathematical Logic, 3rd Ed," Elliot
Mendelson, Wadsworth&Brooks/Cole, 1987, pp 132-149.
Except for some of the base routines, all functions have the declaration
int foo(int n, int* args)
The pointer argument indicates the first in a variable length list of
integer args. Argument n is the length of the list. Increment args in the
body of foo to access each succesive variable. The function returns the
value it computes.
*/
/* The following are used for profiling */
#ifdef PROFILE
int Z_calls;
int N_calls;
int substitute_calls;
int project_calls;
int recurse_calls;
int mu_calls;
int add_calls;
int mult_calls;
int power_calls;
int one_calls;
#endif
/* Base functions */
/* Z: the zero function */
int Z( int n, int *x){
#ifdef PROFILE
Z_calls++;
#endif
return 0; /* This is an easy one */
}
/* N: the successor function */
int N( int n, int *x){
#ifdef PROFILE
N_calls++;
#endif
return (*x) + 1;
}
/* The projection functions. Since there are infinitely many of these, we
must cheat a bit by including an extra variable in the declaration to
select which projection. Thus, strictly speaking the following is really
a schema, or rule, for constructing projection functions. */
int project(int n, int i, int *x){
#ifdef PROFILE
project_calls++;
#endif
return x[i-1];
}
/* The composition rule: we are allowed to form
f(h_1(x_1...,x_n), h_2(...), ... , h_n(...))
from recursive functions f and h_1, ..., h_n. */
int substitute(int n, int *x, int(*f)(int, int *), int(**h)(int,int *)){
int *hvals, rval, i;
#ifdef PROFILE
substitute_calls++;
#endif
/* Allocate and fill array of return values to pass to f */
hvals = (int *)malloc(n*sizeof(int));
for(i=0;i