## Monday, April 17, 2006

### 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.

Is this tail recursion?

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

`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;}`

This post is a part of the selected archive. Karthik said...

I'm not a programmer, But I've given my try. Let me know if I made some mistake.

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

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

Tail Recursive version :

int sum(int n)
{
if(1=n) return 1;
else{
return n+sum(n-1);
}
}

By the way. I'm not sure how I landed on your blog, but its interesting.

Unknown said...

I wonder if python is legal in this board :)

def sumOfFirstNnumbers(n):
....if n = 0:
........return 0
....return n + sumOfFirstNnumbers(n-1)

I just realized your blog does not treat white spaces well.