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?

{
return NULL;
} else if (head->data == dataToFind) {
} else {
}
}

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.