0

I've several confusion about tail recursion as follows:

  1. some of the recursion functions are void functions for example, 
// Prints the given number of stars on the console.
// Assumes n >= 1.
void printStars(int n) {
    if (n == 1) {
        // n == 1, base case
        cout << "*";
    } else {
        // n > 1, recursive case
        cout << "*";        // print one star myself
        printStars(n - 1);  // recursion to do the rest
    }
}

and another example:

// Prints the given integer's binary representation.
// Precondition: n >= 0
void printBinary(int n) {
    if (n < 2) {
        // base case; same as base 10
        cout << n;
    } else {
        // recursive case; break number apart
        printBinary(n / 2);
        printBinary(n % 2);
    }
}

As we know by definition tail recursion should return some value from tail call. But for void functions it does not return any value. By intinction I think they are tail recursion but I am not confident about it.

another question is that, if a recursion function has several logical end, should tail recursion come at all logical ends or just one of the logical ends? I saw someone argued that only one of the logical ends is OK, but I am not sure about that. Here's my example:

// Returns base ^ exp.
// Precondition: exp >= 0
int power(int base, int exp) {
    if (exp < 0) {
        throw "illegal negative exponent";
    } else if (exp == 0) {
        // base case; any number to 0th power is 1
        return 1;
    } else if (exp % 2 == 0) {
        // recursive case 1: x^y = (x^2)^(y/2)
        return power(base * base, exp / 2);
    } else {
        // recursive case 2: x^y = x * x^(y-1)
        return base * power(base, exp - 1);
    }
}

Here we have logical end as tail recursion and another one that is not tail recursion. Do you think this function is tail recursion or not? why?

elias
  • 849
  • 13
  • 28
Lake_Lagunita
  • 521
  • 1
  • 4
  • 20
  • possible duplicate of [What is tail-recursion?](http://stackoverflow.com/questions/33923/what-is-tail-recursion) – Marki555 Jul 10 '15 at 19:17
  • please don't insert hard-copies of code but quoted text (shifted by four spaces in front of the text). – ikrabbe Jul 10 '15 at 19:18
  • You are just asking if that function can be named tail recursion? I don't think there is a script definition if all ends or only some ends have to be "tail" for the func to be called tail recursion... – Marki555 Jul 10 '15 at 19:19

0 Answers0