We discussed Insertion sort in detail earlier. This post shows the recursive implementation of Insertion Sort. Continue reading »

Given a string, print the variation of string as shown below

**Input String:** ‘hat’

- Replace one character with numeric one(‘1’): ‘1at‘, ‘h1t‘, ‘ha1‘
- Replace two characters with ‘1’ each: ‘11t‘, ‘h11‘, ‘1a1‘
- Replace three characters with ‘1’ each: ‘111‘

In all the strings above, wherever the numeric characters are consecutive, add them. So ’11t’ will become ‘2t’, Similarly ‘111’ will become ‘3’. So the final output will be

hat ha1 h1t h2 1at 1a1 2t 3

We discussed problem of Tower of Hanoi earlier and written a recursive function to solve the problem, Recursive functions take lot of extra memory (New activation record for each call on the stack) (A detailed analysis of recursion is done in this post of mine).

Todays question is to write a Non-recursive function to solve problem of Tower Of Hanoi.

The function should not take more than O(n) time (n = number of Moves actually required to solve the problem) and O(1) extra space.

The signature of the function will be

/* The three char represents the characters representing three rods * and n is the number of discs (initially in s) */ void towerOfHanoi(char s, char d, char e, unsigned int n)

Write a recursive function which will print an array in forward and backward order (depending on a parameter). The signature of the function should be

/* If the array is 1 2 3 4 5, then Output should be * 1 2 3 4 5 - if (forward == true) * 5 4 3 2 1 - if (forward == false) */ void printArray(int * arr, int n, bool forward);

We have already seen the problem to reverse the words in a string, in the solution to that problem we have also written function to reverse the string. That was a non-recursive (iterative) function. Write a recursive function to reverse the String.

**For example:** If the String is “ABCD” then the output should be “DCBA“.

Before getting to the solution, please note that a non-recursive solution is always better than a recursive solution in terms of its time and space complexities. To know more about recursion refer this post.

Continue reading »

Given the following structure of Node of the Linked List:

struct Node{ int data; Node *link; };

What is the purpose of the below function

void myFun(Node* head) { if(NULL == head){ return; } printf("%d ", head->data); if(head->link != NULL ) myFun(head->link->link); printf("%d ", head->data); }

Earlier I talked about Reversing a Singly linked list without using recursion. Today let’s write a recursive function to reverse a singly linked list.

Continue reading »

What is recursion? What is head-recursion and tail-recursion? Should we use recursive or non-recursive functions? Continue reading »