1

I'm trying to write a tail-recursive function of the Hofstadter sequence defined like this:

enter image description here

So far I've been able to write a recursive funcion which isn't tail-recursive:

int f_h(int n)
{
    int h;
    if(n==0){
        return 0;
    }
    h = f_h(f_h(f_h(n-1)));

    return(n-h);
}
Mathieu
  • 8,840
  • 7
  • 32
  • 45
Lorenzo Atzeni
  • 21
  • 3
  • 1
    That doesn't look correct -- `h` is never used after being assigned! –  Nov 09 '17 at 23:25
  • How about simply `return n - f_h(f_h(f_h(n - 1)))`? – Some programmer dude Nov 09 '17 at 23:26
  • 1
    Oh and you should probably change the type from `int` to `unsigned`, to satisfy the requirement that `n` can't be negative. – Some programmer dude Nov 09 '17 at 23:26
  • 1
    @Someprogrammerdude still not tail recursive. the chose between int and unsigned is not really the problem here. – Lorenzo Atzeni Nov 09 '17 at 23:30
  • @duskwuff now is correct – Lorenzo Atzeni Nov 09 '17 at 23:34
  • So you updated the question with the correct version, making this whole question *worthless*? If you figured out the problem, add it as an *answer* instead. Or if you got it from a comment, maybe ask the person posting the comment to post an answer? – Some programmer dude Nov 09 '17 at 23:35
  • And the function in the image is `n - H(H(H(n - 1)))`, not `H(n - H(H(H(n - 1))))`. – Some programmer dude Nov 09 '17 at 23:36
  • 1
    @Someprogrammerdude now the function is working, but still isn't tail recursive. I had written that cleary. (sorry for the mistakes, I was modifing the funcion and I made a mess.) – Lorenzo Atzeni Nov 09 '17 at 23:36
  • @LorenzoAtzeni Are you saying that the last line as to be `return f_h();` by itself or does it just have include the call to `f_h()` like Someprogrammerdude's comment does? – twain249 Nov 09 '17 at 23:39
  • @twain249 The last line has to contain only the call to the funcion itself. Otherwise it isn't tail recursive. – Lorenzo Atzeni Nov 09 '17 at 23:42
  • 3
    @LorenzoAtzeni. You're going to have to modify your parameter list. For pure tail recursion you need to take in the current value. See https://stackoverflow.com/questions/33923/what-is-tail-recursion – twain249 Nov 09 '17 at 23:49
  • @twain249 the problem here is that this sequence is due to the fact that i have to call the funcion more than one time. I don't undestand how can I modify the parameters in the proper way. – Lorenzo Atzeni Nov 10 '17 at 00:08

0 Answers0