• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

The math nature of a primitive recursive function

 
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 1090
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Ellen
Maybe because of overflow.
 
Ellen Zhao
Ranch Hand
Posts: 581
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic