programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# The math nature of a primitive recursive function

Ellen Zhao
Ranch Hand
Posts: 581
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

Anupam Sinha
Ranch Hand
Posts: 1090
Hi Ellen
Maybe because of overflow.

Ellen Zhao
Ranch Hand
Posts: 581
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

David Weitzman
Ranch Hand
Posts: 1365
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
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 ]