aspose file tools*
The moose likes Programming Diversions and the fly likes The math nature of a primitive recursive function Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "The math nature of a primitive recursive function" Watch "The math nature of a primitive recursive function" New topic
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 ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: The math nature of a primitive recursive function
 
Similar Threads
Question about mem allocation for recursive functions
Recursion Reciprocals
return - problem
Recursion
Iterative Fibonacci Method Problem