1) Find and discuss an interesting example of recursion - thus, an example other

Question

1) Find and discuss an interesting example of recursion - thus, an example other than those presented in the readings.

Your discussion should:

give citations,

make it clear that this is either a head or tail recursion algorithm, and

include both space and time big-O performance estimates of your example.

(2) Propose a linear representation protocol of a binary tree data structure.

An example is RPN (reverse Polish notation) where a b + c * d e f + * / is a representation of the following tree:

Thanks for your help.

Explanation / Answer

1) Reverse a stack using recursion: To reverse a stack we need to pop element one by one. After calling pop fuction of stack, call the recursive function and then for each poped element we need to insert at the bottom of the stack (to get the reverse stack. try with pencil and paper then you will understand).

Algo:

Revers_stack(stack st)

{

int val= pop (st);

Revers_stack(st);

insert_at_the_bottom(st,val);

}

its time complexity is O(n^2) (where n is the number of elements are present in the stack)because for each stack element recursion is call and for each recursion insert_at_the_bottom function is called which is again O(n). Hence, it is O(n^2).

A call is head-recursive if the first statement of the function is recursive call. In head recursion, the recursive call, when it happens, comes before other processing in the function

A call is tail -recursive if nothing has to be done after the recursive function call. i.e. when the call returns, the returned value is immediately returned from the calling function.

This recursion looks like head-recursive because main processing part(i.e. calling of insert_at_the_bottom) occurs after the function call

cite: http://www.geeksforgeeks.org/reverse-a-stack-using-recursion/

2) We can represent binary tree by an array representation. If the index of current node in the array is i then the left child is calculated by formula 2*i and right child is calculated by formula 2*i +1. This is not very space efficient. For full binary tree this representation is preferable but for skewed binary tree it is not preferred. For a tree of height h, an array of length 2^(h +1) -1 is required.

for more information refer this link:

http://www.btechsmartclass.com/DS/U3_T31.html

if any other help is required on this question then let me know

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.