# The math nature of a primitive recursive function

Ellen Zhao

Ranch Hand

Posts: 581

posted 12 years ago

My original work was to prove a function is primitive recursive by means of lambda notation, then use the conclusion to prove another function is mju: recursive. I wrote the program just for fun after I cleared the proof. The function is described in the program. Now the output log interests me, you can see, for some combination of x and n, the recursion counter returns a value of 3*(recursionCounter(n-1)) + 1, for example, when x = 0 and n = 0 to 19, this rule holds; but when x = 0, n = 20, this rule fails. Interesting. I believe the recursion counter's value is regulary, it depends on the combination of x and n. But it seems now a mystery to me, anyone knows the relationship between the parameter n, x, the function value and the recursion counter's value? Thanks in advance.

Regards,

Ellen

Regards,

Ellen

Ellen Zhao

Ranch Hand

Posts: 581

posted 12 years ago

Bingo. The type of the recursionCounter should be long. Thank Anupam.

I think I didn't make myself understood. Observe the value of recursion's counter you will see for some n and x, the recursionCounter is very very "primitive", some even less 100. But for some n and x, say, let x = 0 and n larger than 20, the value is no longer so "primitive". I want to know the relationship between n, x and the value of recursionCounter(for which x, n, can the counter be large and for which x, n, can the counter be small). Thanks.

Regards,

Ellen

I think I didn't make myself understood. Observe the value of recursion's counter you will see for some n and x, the recursionCounter is very very "primitive", some even less 100. But for some n and x, say, let x = 0 and n larger than 20, the value is no longer so "primitive". I want to know the relationship between n, x and the value of recursionCounter(for which x, n, can the counter be large and for which x, n, can the counter be small). Thanks.

Regards,

Ellen

David Weitzman

Ranch Hand

Posts: 1365

posted 12 years ago

If you modified the method so that recursion(x, n-1) is called either 0 or 1 times per method invocation and not more, it would be a lot easier to track (in addition to being more efficient). As it is, the fact that recursion() can be recursively called a different number of times in each method invocation is enough to drive a person slightly batty.

Ellen Zhao

Ranch Hand

Posts: 581

posted 12 years ago

The modified version 1.1. More tracking of which condition does the function enter has been added. Since the function always returns 1 once it reaches the value 1, a break statement has been added in the loop in the main method.

Still caculating...the server of our school seems a bit slow...

[ July 11, 2003: Message edited by: Ellen Zhao ]

Still caculating...the server of our school seems a bit slow...

[ July 11, 2003: Message edited by: Ellen Zhao ]