ISRO2018-69

Question

Let $P$ be a procedure that for some inputs calls itself (i.e. is recursive). If $P$ is guaranteed to terminate, which of the following statement(s) must be true?

1. $P$ has a local variable
2. $P$ has an execution path where it does not call itself
3. $P$ either refers to a global variable or has at least one parameter 

1. I only
2. II only
3. III only
4. II and III only

Answer 1

It is said that the recursive procedure p will terminate ultimately.If p don't have any parameter or don't refer to any global variable then p will consist of only local variables.So each time when p will recursively be called then a new copy of local variables will be created in the stack.In this case we can't track howmany times p  is called till now.So p have to refer atleast one global variable or take atleast one parameter.

Along with that we have to use the global variable or the parameter by imposing a condition that when p will not call itself.At that time only p will terminate.

So D is correct option.

Comments

if it has a static variable instead of global variable then also valid. are we considering static under global variable??

---

I didn't get your explanation for III. and not convinced why it is one possible reason for termination. Could someone please explain..:)

---

Basically you can think of a scenario where function P() calls Q() and the return value of Q() is compared with termination condition or after execution of Q(), P() simply terminates...