Recursion

[Francis Siu]

Hi Ilja Preuss and ranchers
I have some psudo-code that describe a recusion, but I do not know whether it will stop or not. Is it missing the base case?

 
//Q is a queue
Reverse(Q)
{
  if (!isEmpty(Q))
    temp=delete(Q)  //dequeue the element in queue and assign to temp
  Reverse(Q)
  add(Q,temp) //Will it never arrive?
}
 

thanks for your time
Regards

[Ernest Friedman-Hill]

As I read this, Reverse() calls itself every time it is called, so no, it will never stop. Are there some missing braces that belong with the "if" statement?

[Francis Siu]

thanks Ernest
I do not know too ^o^ as I just copy the answer given from TA and then smile
I think that only version 1 works
Version 1

 
//Q is a queue
Reverse(Q)
{  
  if (!isEmpty(Q))
  {    
    temp=delete(Q)  //dequeue the element in queue and assign to temp
    Reverse(Q)
  }
  add(Q,temp) //Will it never arrive?
}

Version 2

 
//Q is a queue
Reverse(Q)
{  
  if (!isEmpty(Q))
  {    
    temp=delete(Q)  //dequeue the element in queue and assign to temp
  }
  Reverse(Q)  
  add(Q,temp) //Will it never arrive?
}

Version 3 (Original version) ambiguous one

 
//Q is a queue
Reverse(Q)
{  
  if (!isEmpty(Q))
    temp=delete(Q)  //dequeue the element in queue and assign to temp
    Reverse(Q)  
    add(Q,temp) //Will it never arrive?
}

Do the above three version work?
I wonder that is the program missing the base case?
thanks ^o^
[ December 11, 2004: Message edited by: siu chung man ]

[Jim Yingst]

For version 3, I think you need to establish where the braces should be. This is pseudocode after all, so probably you're expected to infer the block structure from indentation. I suspect it's intended to be:

Reverse(Q)
{  
  if (!isEmpty(Q))
  {
    temp=delete(Q)  //dequeue the element in queue and assign to temp
    Reverse(Q)  
    add(Q,temp) //Will it never arrive?
  }
}

For all three of these, you should be able to determine what happens by analysis. For each one: what happens if Q has length 0? What about length 1? Or length 2? Of course, if an algorithm is broken for 0 or 1, you don't really need to analyze any more, I think.