Let n be a positive integer. We will consider words with n letters, written w_1,
ID: 3825295 • Letter: L
Question
Let n be a positive integer. We will consider words with n letters, written w_1, w_2..w_n, where each letter w_i, is a letter from the English alphabet. Define the reversal of the word [w_1, w_2, ..., w_n] to be the word with the same letters in reverse order, Suppose we want to compute the reversal of an input word [w_1, w_2..., w_n], Here is an iterative algorithm to do so: IterReverse ([w_1, w_2, ..., w_n]) for i = 1 to n: v_i = w_n_i+1 return [v_1, v_2, ..., v_n] Assume that a structure to hold the output [v_1, v_2, ..., v_n] exists and has been appropriately initialized.Explanation / Answer
Hi,
Please find the answer to the question below:-
I have written the algo and also I have provided proper comments wherever necessary to understand the algo.
An example is also given so that recursion can be understood.
=======================================================================================
Recursive algorithm
Assume ALL WORDS ARE initialized globally
Global initialization (W1, W2, W3…..Wn)
int n=1; //initialize subscript to 1;
int i=0; //initialize subscript to 0;
RecursAlgo (Word Vi)
{
i=i+1
If (Vi==W4)//Base condition when the word becomes equal to last word then exit recursion
{
Return W4 //and return the last word.
}
Else //Or else assign the incremented word to Variable Word Vi increment the value of subscript of word n and recursively call REcursAlgo
{
Vi=Wn
n=n+1;
return RecursAlgo (Vi)
}
//The Recursion will be called from main function as:-
Main
{
Word=RecursAlgo (W1)
}
======================================================================================
Example:-
Lets way we have word list as(W1,W2,W3,W4)
With recursion when recursion takes place the stack will be pushed up with variables V1=W1,V2=W2,V3=W3,V4=W4 having the values of word in them as:-
V4
V3
V2
V1
Now when the function return to main then the values will be popped in LIFO manner and will print in recursive manner V4, V3, V2, V1.
V4
V3
V3
V2
V2
V2
V1
V1
V1
V1
========================================================================================
Please let me know in case of any clarification.
V4
V3
V2
V1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.