Recursion Part 3: Exercises in tail recursion

The following is a part of a series of articles I had written on recursion.

---

This part provides some exercises related to the concepts introduced in the previous part.

All Parts:

Recursion Part 1: Introduction to recursion
Recursion Part 2: Tail recursion, Accumulators and Iteration
Recursion Part 3: Exercises in tail recursion
Recursion Part 4: Tree Recursion and Dynamic Programming
Recursion Part 5: Structural and Generative Recursion
Recursion Part 6: References and Further Information

---

Try out the following problems: Ask any questions/answers in the comments.

Is this tail recursion?

int fibonacci(int n)
{
    if (n <= 2) {
        return 1;
    } else {
        return fibonacci(n - 2) + fibonacci(n - 1);
    }
}

What about this?

node findRoot(node child)
{
    if (NULL == child->parent) {
        return child;
    } else {
        findRoot(child->parent);
    }
}

And this?

node findNodeInList(node head, int dataToFind)
{
    if (NULL == head) {
        return NULL;
    } else if (head->data == dataToFind) {
        return head;
    } else {
        return findNodeInList(head->next);
    }
}

---

Try converting the above three programs to iterative versions. Do you find some harder than the others?

---

Convert this iterative program into a tail recursive version. First convert it to an accumulator based function and then convert that to an ordinary tail recursive version. Hint: First convert the for loop into a while loop.

int sumOfFirstNnumbers(int n)
{
    int i = 0, sum = 0;

    for (i=1; i<=n; i++) {
        sum += i;
    }
    return sum;
}

How about this one? Assume all numbers are positive (> 0). Hint: The accumulator does not always have to perform some mathematical operation. It can also be used to keep track of the state so far.

int findMax(int *numberArray, int arrayLength)
{
    int i = 0, max = 0;

    for (i=0; i<arrayLength; i++) {
        if (max < numberArray[i]) {
            max = numberArray[i];
        }
    }
    return max;
}

---

Any questions? Comments? Please leave a comment using the comment form below.

This post is a part of the selected archive.