Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

DarkBASIC Discussion / Recursive function question

Author
Message
No Time To Code
15
Years of Service
User Offline
Joined: 22nd Dec 2008
Location:
Posted: 13th Sep 2010 02:48
I'm trying to understand recursive functions. The following code was taken from the 6/08 newsletter and I just added a print command in the function.



I would have thought that when you run it, you would see it print a 1 and then print XXXXXXXXXX. It actually prints the numbers 1-11 and then XXXXXXXXXX. I thought that the first line of the function would keep calling the function over and over until the LEN > 10 and never get to the ct(0) = ct(0)+1 and Print ct(0) lines of code until after the LEN > 10.

This is actually the behavior I wanted to see for what I'm going to try (a Minimax function for TicTacToe), but I want to understand why this happens.

It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard to their own interest. --Adam Smith
BN2 Productions
20
Years of Service
User Offline
Joined: 22nd Jan 2004
Location:
Posted: 13th Sep 2010 03:37 Edited at: 13th Sep 2010 03:38
It is printing the numbers 1-11 because of the line

Print Ct(0)

Here is your function linearized:


Now this is a bear and I haven't tested it (probably missed an endif or something).

The idea here is just to see it.

An ENDFUNCTION command works just like a RETURN command, that is, it will return you to the line after the line that called the function. So basically every function that is started (or every instance of the same function) has to be completed in order before going all the way back to the original call.

Make any sense?

Great Quote:
"Time...LINE??? Time isn't made out of lines...it is made out of circles. That is why clocks are round!" -Caboose
Latch
17
Years of Service
User Offline
Joined: 23rd Jul 2006
Location:
Posted: 13th Sep 2010 03:51 Edited at: 13th Sep 2010 03:51
Maybe this will help show how the function is being called. I've added another function that will count up each time the first function is called. Like BN2 said, you'll see each call to myfunc has to be completed before the function moves on.



Enjoy your day.
No Time To Code
15
Years of Service
User Offline
Joined: 22nd Dec 2008
Location:
Posted: 13th Sep 2010 05:15
BN2 and Latch,

I'm trying to get my head around this, so whenever a function is called, it has to run until it hits a ENDFUNCTION or EXITFUNCTION command? So in this case it gets called 11 times before the condition is satisfied that allows it to continue to completion. So the remainder of the code:

then runs 11 times and before the ENDFUNCTION s$ line is reached.

I think I'll need to sleep on this one!
Thanks for the quick response.

It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard to their own interest. --Adam Smith
BN2 Productions
20
Years of Service
User Offline
Joined: 22nd Jan 2004
Location:
Posted: 13th Sep 2010 05:40
Remember, ENDFUNCTION works just like the RETURN command. So once you hit it, it will go to the line after the call, which means that for all iterations except the very last one, you are going to line 2 of your function which is Ct(0)=Ct(0)+1.

Think of it like a Russian Nesting Doll. Cut it in half so that you can see every piece. Now, Starting from the top and going down it looks something like this:

First Top
Second Top
Third Top
Fourth Top
Fourth Bottom
Third Bottom
Second Bottom
First Bottom

Where first, second, third, and fourth represent the first, second, third, and fourth doll that you encounter on your trip down.

Think of each iteration of the loop (every time you call the function before the first call has been completed) as the next doll that you encounter. You cannot reach the bottom of the first doll before you hit the bottom of the second, third, fourth, etc dolls first.

Make any more sense?

Great Quote:
"Time...LINE??? Time isn't made out of lines...it is made out of circles. That is why clocks are round!" -Caboose
No Time To Code
15
Years of Service
User Offline
Joined: 22nd Dec 2008
Location:
Posted: 13th Sep 2010 05:56
Quote: "Make any more sense?"

Yes, it is starting to make some sense. It wasn't so much the russian doll analogy as much as:

Quote: "So once you hit it, it will go to the line after the call, which means that for all iterations except the very last one, you are going to line 2 of your function which is Ct(0)=Ct(0)+1."


That's when it started to sink in. I'm going to have to be very careful when I try to implement this in the game because I can see how it could quickly become convoluted.

Thanks so much!

It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard to their own interest. --Adam Smith
Libervurto
17
Years of Service
User Offline
Joined: 30th Jun 2006
Location: On Toast
Posted: 13th Sep 2010 16:20
I wrote this cool little program a while ago. It solves the towers of hanoi puzzle using recursive functions. A lot of the code is actually out of a book so I can't take full credit for it.


Latch
17
Years of Service
User Offline
Joined: 23rd Jul 2006
Location:
Posted: 13th Sep 2010 17:43
Quote: "I'm trying to get my head around this, so whenever a function is called, it has to run until it hits a ENDFUNCTION or EXITFUNCTION command?"


If you run the code I posted, you'll see that the countit() function gets run 11 times before ct(0)=ct(0)+1 is executed in myfunc(). myfunc() keeps restarting itself as long as the conditional:

IF LEN(s$)<10 THEN s$=myfunc( s$+"X")

is met.

Each time the function is called, the function address is stored on the stack (a temporary storage place in the computers memory) and the current line is managed by the program counter (PC). The PC keeps track of the current line and looks at the stack to see if there were any jumps that it has to return to. A function call is one such jump. A gosub and return is another such jump. A goto, is a jump without any kind of return - therefore the PC is set to the goto's destination without having to store anything on the stack.

In the case of your function, there are 11 jumps that occur before the PC can move on to ct(0) = ct(0) +1 . Once the PC has been able to move on to that line, it will reach the endfunction. Once this is hit, the PC will look at the stack and say "where was this call made from?"

If there is an answer, the PC will reset to the end point of the command on the line from where it was called (usually ends up being the next line after the call - but don't take this literally). Since ':' in BASIC can string multiple commands together, the PC doesn't necessarily have to return to the next physical line after the one it was called from:



In this example, Print "a = ";a is executed after 19 recursive calls to _add. The : is a marker to tell the PC where to return. Each time the Return is hit, the PC will look at the stack and ask if where the call came from. Every time the PC asks the stack a question, the stack gives the answer and reduces itself. It removes the top entry. In effect in the last example, after the stack has stored 19 calls, it will reduce that number by 1 call each time it is queried by the PC until there is no more information to give, at which time the PC will move beyond the function or the subroutine.

In this way, functions and subroutine calls can be nested within each other.

Now, there is only a certain amount of memory that the stack can use, so if you have a recursive call that gets nuts, or doesn't have a resolution, it's easy to crash the computer. That's one reason it's bad to use a GOSUB without a return. The stack might have information on it that never gets removed.

Loops might be subject to this as well. If you don't let the loop resolve, and you jump out of it with a goto for example, the stack may have information on it that never gets used (removed). That's why it's important to use EXIT to break out of a loop if you have to. I would bet that Exit clears the stack and resets the PC.

Enjoy your day.
No Time To Code
15
Years of Service
User Offline
Joined: 22nd Dec 2008
Location:
Posted: 13th Sep 2010 17:59
@OBese87
I'll take a look at your Towers program when I get home today.

@Latch
I did run your code last night and your explaination today makes things a lot more clear. Now a feel more comfprtable trying to tackle the Minimax algorithm.

Thanks


It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard to their own interest. --Adam Smith

Login to post a reply

Server time is: 2024-04-19 07:38:28
Your offset time is: 2024-04-19 07:38:28