Topic awaiting preservation: Insomnia & recursion (Page 1 of 1)

I'm having insomnia today, actually tonight.
All due to a mid-term exam that I did in the evening.

One of the questions that I had to answer was: what is the maximum number of times that 'return' can be used inside a recursive method?

My answer was that there is no limit but I am afraid that maybe the correct answer is TWO.
What do you think?

I'd rather say ONE, since once the return instruction is executed, the method stops and the process goes back to the calling instruction.

Mathieu "POÏ" HENRI

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

Except that a return in some languages can act like break in PHP...it only breaks one level...if you have a recursive recursive function, then you have to use a return for each nested statement

The poster has demanded we remove all his contributions, less he takes legal action.
We have done so.
Now Tyberius Prime expects him to start complaining that we removed his 'free speech' since this message will replace all of his posts, past and future.
Don't follow his example - seek real life help first.

Skaarjj: We're talking about the number of return statements being *executed*, not their count in a method.
It's obvious that if your method have several exit conditions, it'll have several return statements, but only one will be executed.

Mathieu "POÏ" HENRI

^^ right on

~Sig coming soon~

The return can be run once per function, but it will return the program to the previous method. So if you have the function call it self (recursive) the function as a group can execute the return as many times as it want, but each instance of the method will only be able to execute the retun once.

_________________________
"There are 10 kinds of people; those who know binary, those who don't and those who start counting at zero"
- the Golden Ratio -

Besides having insomnia last night, I wasn't also able to enjoy my sleep for too much time. Here I am waken up already, having slept only around 4 hours. I didn't have to wake up, I could have slept as long as I wanted, but for unkonwn reasons to me, I just wake up and can't sleep again.

Enough complaining. First of all, now that I have my mind better rested, I re-read this post to find out that I AM AN IDIOT.

I described the question wrongly. Sorry folks.

The question was not how many return statements I can have in a recursive method (BTW, I think you all are misinterpreting my wrong question but since it's the wrong question misinterpreting it will do no harm, right?).

Let me try to explain the question.
The question was: inside a recursive method, how many times can you call it recursively?

For instance, in this piece of code:

static LLNode revert(LLNode previous, LLNode current)

    {

        if (current == null)

            return previous;

        LLNode next = current.next;

        current.next = previous;

        return revert(current, next);

    }

I am calling recursively revert() only once.
In this other piece of code:

static void removeDup(LLNode current)

    {

        if ((current == null) | | (current.next == null))

            return;

        if (current.val == current.next.val)

        {

            current.next = current.next.next;

            removeDup(current);

        }

        else

            removeDup(current.next);

        return;

    }

I am calling removeDup() twice, inside removeDup().

Can I have a method that calls itself three times, for instance?
My answer was that I can have as many recursive calls to the method (inside the method) as we may wish.

Am I right?

PS - sorry for the mistake of asking you the wrong question. I hope I am clearer now.
I

Yup, you can have as many as you want.

ok, I'm no programmer but, I think that what poi said:

"It's obvious that if your method have several exit conditions, it'll have several return statements, but only one will be executed."

still holds true.

You can have the call in your function as many times as you want (I would think) but, it is only going to be executed once. Right?
From your example, since it is conditional, the condition can only be one. At this point the code will be executed which is calling itself.
Eigh...boy this is confusing.......

But, I don't think you're an idiot viol. If that is the only question that is bothering you, how many questions were on the exam? Don't beat yourself up over it.

Later,

C:\


~Binary is best~

viol: The answer you gave to the second question seems correct. I wonder if the question means "how many times can the function recurse?"

For example:

int 

   Factorial(int x)

     {

       if  (x <= 1) return(1);



      return(x*Factorial(x-1));

     }

for this code the question would be "what is the largest number x can be when you call Factorial".

The maximum number of times this function can recurse depends on the stack size.

You can recurse a function until you run out of stack space.



-- not necessarily stoned... just beautiful.

This was the first question of the exam. It worths 5 points out of 100. It's just a small part of it, but it's enough to bother me. This is just me, I can't help it.

There were other 9 multiple questions, besides this one, that I _believe_ I have answered all of them right.

Besides the multiple choice questions, there were also some programming to do. From these, there is one that I believe I may have screwed up but this one I already know what I should have done. Actually, it's about how to remove duplicates from a sorted linked list (with integers inside the nodes), and the answer that I could have done is the code shown above as the method removeDup(). After getting home, I sit and came up with this recursive code that I know works fine (because I tested it). In the exam, I didn't use recursion, I opted for an iterative version of it (and there I may have made some mistakes). I don't feel comfortable writing recursive methods without having my computer at hand to test it so, in the exam, I tried to stay away from recursion.

The problem in these exams is not coming up with the right answer but coming up with the right answer in the right time.

<EDIT> hyperbole: in a factorial recursive method we must also be aware of the limit of the variable being used. If it's an int, we can't go further than around 2 billions, I think. So, before running out of stack (that usually is huge), we will run out of bits in the variable itself to represent the number. </EDIT>

[This message has been edited by viol (edited 10-30-2003).]

You beat me to it Hyperbole. I agree completely with you.

Assuming that we are talking about proper re-entrant code, you can call a recursive function

int( (stack-size - currently-used-stack-space) / (re-entrant-data + return-address) )

times - so the number of calls is dependant on

1) the stack size (which already differs between both machines and language implementations)
2) the number, sizes and types of data being pushed onto the stack at each call
3) to a lesser extent the byte-size of the return address (stacked last if I remember correctly).

Modern languages may only push the address and size of the re-entrant data items, not the data itself, some even just push the location and size of a single structure to be 'reconstituted' on return. This makes them considerably more stack-efficient, but the same rule still applies. Programming just one decent, small applictaion in Hex or Assembler would make this sort of thing considerably easier to understand.

As Hyperbole says - The stack's the limit.


Bug-free software only exisits in two places
A programmer's mind and a salesman's lips

Trust Skaarjj to go shitting on about something...

"You know you have been doing 3d too long when you walk into a church and think, "God, the polycount of this place must be huge!"