Flickr Badge

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.

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.

2 comments:

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.