JavaRanch » Java Forums »
Other »
Programming Diversions
| Author |
The math nature of a primitive recursive function
|
Ellen Zhao
Ranch Hand
Joined: Sep 17, 2002
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
Joined: Apr 13, 2003
Posts: 1088
|
|
Hi Ellen
Maybe because of overflow.
|
|
Ellen Zhao
Ranch Hand
Joined: Sep 17, 2002
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
Joined: Jul 27, 2001
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
Joined: Sep 17, 2002
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 ]
|
|
 |
|
|
subject: The math nature of a primitive recursive function
|
|
|
|
0
