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

## 3 comments:

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.

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.

Sir i found your entire series on Recursion. I thank you a ton for writing this wonderful article. I am facing problem in coding "

findMax"without using accumulator variable. I would be glad if you provide solution.Thanks

Post a Comment