• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

Need help with a simple piece of Lua code.

Status
Not open for further replies.
Level 11
Joined
Oct 11, 2012
Messages
711
JASS:
function f(n)
	if n == 0 then return 0
	else
		local res = f(n - 1)
		print(n)
		return res
	end
end

print (f(5))

The print out of this piece of code is:
1
2
3
4
5
0

However, I don't understand why... My questions are:
1. Shouldn't the first number be "5" ?
2. The variable "res" is a function, right?
3. Why there is a loop?
 
Level 23
Joined
Apr 16, 2012
Messages
4,041
lets check what it does.

1. You pass in 5, the first check fails, so you go to if body.
2. There, you try to initialize "res" into f(4).
3. step 1 with 4 as value
4. step 2 with 4 as value
5. step 1 with 3 as value
6. step 2 with 3 as value
7. step 1 with 2 as value
8. step 2 with 2 as value
9. step 1 with 1 as value
10. step 2 with 1 as value
11. you now work if input of 0, so the first check passes and returns 0

The callstack is as follows:

(oldest to newest call)
call f(5)
call f(4)
call f(3)
call f(2)
call f(1)
call f(0) -> returns

therefore, we are now back in the call to f that got 1 as n.
Here, we print 1, and return 0, because the res is initialized to 0.

After that, the res of the f(2) is set to 0 and prints its n, which is 2 and returns 0.

This goes on and on until 5, and then finally returns 0, therefore you have 0 at the end.


I hope this helped you

edit: to answer all the questions, res is integer, because the function f returns integer(0 implicitly says it should be integer, but in Lua I dont know if it could be probably anything).

This is a loop called recursive function calls. This is helpful to write easier to read and to write code for stuff like fibonnachi's sequence
 
Level 11
Joined
Oct 11, 2012
Messages
711
lets check what it does.

1. You pass in 5, the first check fails, so you go to if body.
2. There, you try to initialize "res" into f(4).
3. step 1 with 4 as value
4. step 2 with 4 as value
5. step 1 with 3 as value
6. step 2 with 3 as value
7. step 1 with 2 as value
8. step 2 with 2 as value
9. step 1 with 1 as value
10. step 2 with 1 as value
11. you now work if input of 0, so the first check passes and returns 0

The callstack is as follows:

(oldest to newest call)
call f(5)
call f(4)
call f(3)
call f(2)
call f(1)
call f(0) -> returns

therefore, we are now back in the call to f that got 1 as n.
Here, we print 1, and return 0, because the res is initialized to 0.

After that, the res of the f(2) is set to 0 and prints its n, which is 2 and returns 0.

This goes on and on until 5, and then finally returns 0, therefore you have 0 at the end.


I hope this helped you

edit: to answer all the questions, res is integer, because the function f returns integer(0 implicitly says it should be integer, but in Lua I dont know if it could be probably anything).

This is a loop called recursive function calls. This is helpful to write easier to read and to write code for stuff like fibonnachi's sequence

Thanks for the reply, but I still don't get it. :(
1. Why keep repeating "step 1", "step 2", "step 1", "step 2",....?What does it mean?
2. when it tries to initialize "res" for the first time " local res = f(5-1)", shouldn't “print(n)” equals “print(5)”? If so, then ,"5" should be printed out, right?

Edit:
Oh, I think I am getting it. The code execution stops at this line "local res = f(n-1)" and does not go to "print(n)" until "n" reaches "0"?
 
Level 29
Joined
Jul 29, 2007
Messages
5,174
Here's an illustration of the call stack:
Lua:
res = f(5)
|    res = f(4)
|    |    res = f(3)
|    |    |    res = f(2)
|    |    |    |    res = f(1)
|    |    |    |    |    res = f(0)
|    |    |    |    |    return 0
|    |    |    |    print(n) -- 1
|    |    |    |    return 0
|    |    |    print(n) -- 2
|    |    |    return 0
|    |    print(n) -- 3
|    |    return 0
|    print(n) -- 4
|    return 0
print(n) -- 5
return 0

You are using a recursive function. As in, a function that keeps calling itself, while progressing towards some goal, in this case, n == 0 (without a goal, or in other words ending condition that the function progresses to, you will get infinite recursion which would quickly lead to a stack overflow).

Note that you always return 0, which is probably not what you want.

And please use your best friend in the world, Google, before opening a new thread for every tiny issue that was asked twenty trillion times already.
 
Level 11
Joined
Oct 11, 2012
Messages
711
Here's an illustration of the call stack:
Lua:
res = f(5)
|    res = f(4)
|    |    res = f(3)
|    |    |    res = f(2)
|    |    |    |    res = f(1)
|    |    |    |    |    res = f(0)
|    |    |    |    |    return 0
|    |    |    |    print(n) -- 1
|    |    |    |    return 0
|    |    |    print(n) -- 2
|    |    |    return 0
|    |    print(n) -- 3
|    |    return 0
|    print(n) -- 4
|    return 0
print(n) -- 5
return 0

You are using a recursive function. As in, a function that keeps calling itself, while progressing towards some goal, in this case, n == 0 (without a goal, or in other words ending condition that the function progresses to, you will get infinite recursion which would quickly lead to a stack overflow).

Note that you always return 0, which is probably not what you want.

And please use your best friend in the world, Google, before opening a new thread for every tiny issue that was asked twenty trillion times already.

If I knew the search term, I wouldn't bother making a post here asking this stupid question. If asking this kind of question is not allowed on this forum, I will shut up and go to other places where stupied question is not forbiden. Oh, and abviously I am not as smart as you are.
 
Level 29
Joined
Jul 29, 2007
Messages
5,174
If I knew the search term, I wouldn't bother making a post here asking this stupid question. If asking this kind of question is not allowed on this forum, I will shut up and go to other places where stupied question is not forbiden.

This question is ok, but your other threads are just a google search.
Of course you can ask anything you want, but if you end up asking something to which the answer would be the first result of a google search, don't expect me not to be snarky.

Either way, back to the topic, if you want to learn more, "recursion" is your keyword.
 

Dr Super Good

Spell Reviewer
Level 63
Joined
Jan 18, 2005
Messages
27,178
The behaviour you are seeing is basically how stacks work. You are appending stuff to the top of the stack by calling the function (as each call adds a new frame on top of the stack) and then removing from it when you print and return (you print the top, return removes the top frame). You also return a value which cascades down based on when it reaches the far top of the stack of calls.

1. Shouldn't the first number be "5" ?
Only if you inverted the order of printing and calls. If you printed first and then called second then yes, the first will be 5. Eg...

Code:
function f(n)
     if n == 0 then return 0
     else
         print(n)
         return f(n - 1)
     end
 end

 print (f(5))

2. The variable "res" is a function, right?
No, it is a value returned by the function. You need to use a function pointer to represent a function. I am unfamiliar with LUA (usually do C/C++ or JAVA) but I am guessing it would look something like this...
Code:
local res = f
Again, I am not sure if that is valid LUA but the idea for the variable to represent a function is that you give it the function as an argument (its name) and not try and evaluate the function. In C/C++ you need to reference the function with & operator which will convert it into a function pointer.

3. Why there is a loop?
The function calls itself until the condition "n == 0" is reached. This means the function is recursive as it will keep calling itself until a solution or crash occurs. I mention the crash as this is a big problem with recursive functions since if they go too deep they will overflow the stack which will either cause a process crash (modern OS) or BSoD (integrated systems or old OS). Generally you want to avoid recursive function calls where possible as their maximum depth is based on how deep they were called from and the thread stack size. This also makes them not very argument safe (large arguments can cause a crash, if you were to call your function with value 2147483647 your program will probably crash). They are useful as each stack frame can allocate new variables, as such you can take advantage of a stack based allocation system without the need for dynamic memory allocation on the heap however problems that need this seldom occur outside of tree like structures (which never go too deep anyway).

The most famous example of this gone wrong was the WC3 crash hack. If you were to queue over 30k invalid orders onto a unit and have them validate them all at once WC3 used to crash as it would cause a stack overflow due to nested function calls resolving each order. Hackers made a tool to queue up the orders (since that is not humanly possible, it even made a huge amount of lag from network traffic) and then all the user had to do was collapse the order (eg cancel a building) and then boom, everyone crashed. Obviously they used a hacked version of WC3 with larger stack size so they did not crash and they were counted as the winner. Luckily most of these people were banned when they patched the bug.
 
Level 15
Joined
Oct 18, 2008
Messages
1,588
The behaviour you are seeing is basically how stacks work. You are appending stuff to the top of the stack by calling the function (as each call adds a new frame on top of the stack) and then removing from it when you print and return (you print the top, return removes the top frame). You also return a value which cascades down based on when it reaches the far top of the stack of calls.


Only if you inverted the order of printing and calls. If you printed first and then called second then yes, the first will be 5. Eg...

Code:
function f(n)
     if n == 0 then return 0
     else
         print(n)
         return f(n - 1)
     end
 end

 print (f(5))


No, it is a value returned by the function. You need to use a function pointer to represent a function. I am unfamiliar with LUA (usually do C/C++ or JAVA) but I am guessing it would look something like this...
Code:
local res = f
Again, I am not sure if that is valid LUA but the idea for the variable to represent a function is that you give it the function as an argument (its name) and not try and evaluate the function. In C/C++ you need to reference the function with & operator which will convert it into a function pointer.


The function calls itself until the condition "n == 0" is reached. This means the function is recursive as it will keep calling itself until a solution or crash occurs. I mention the crash as this is a big problem with recursive functions since if they go too deep they will overflow the stack which will either cause a process crash (modern OS) or BSoD (integrated systems or old OS). Generally you want to avoid recursive function calls where possible as their maximum depth is based on how deep they were called from and the thread stack size. This also makes them not very argument safe (large arguments can cause a crash, if you were to call your function with value 2147483647 your program will probably crash). They are useful as each stack frame can allocate new variables, as such you can take advantage of a stack based allocation system without the need for dynamic memory allocation on the heap however problems that need this seldom occur outside of tree like structures (which never go too deep anyway).

The most famous example of this gone wrong was the WC3 crash hack. If you were to queue over 30k invalid orders onto a unit and have them validate them all at once WC3 used to crash as it would cause a stack overflow due to nested function calls resolving each order. Hackers made a tool to queue up the orders (since that is not humanly possible, it even made a huge amount of lag from network traffic) and then all the user had to do was collapse the order (eg cancel a building) and then boom, everyone crashed. Obviously they used a hacked version of WC3 with larger stack size so they did not crash and they were counted as the winner. Luckily most of these people were banned when they patched the bug.

Yay recursive fibonacci! :D
 
Level 29
Joined
Jul 29, 2007
Messages
5,174
That snippet performs impractical unsafe type casting. You could equally well set a function pointer to a static address that happens to be the function and it will work. Until you recompile with extra code or different optimizations that is.

Thank you for your continuous derailing of threads.

Also I don't see any unsafe type casting, or any type casting for that matter, so what are you talking about...
 

Dr Super Good

Spell Reviewer
Level 63
Joined
Jan 18, 2005
Messages
27,178
Thank you for your continuous derailing of threads.
Pot, kettle, black...

Also I don't see any unsafe type casting, or any type casting for that matter, so what are you talking about...
When getting a function pointer you should use an ampersand for readability otherwise it could be you are sourcing the function pointer from another variable with that name and not that the function itself is that name. As an editor you will have to resolve which of those cases it is to understand how the code acts. Trying to get the pointer of a variable holding a function pointer will result in a different type, (a pointer to a pointer to a function) so should hopefully throw a compile time implicit casting error if set to a pointer to a function. Not strictly type related however it certainly could cause programming mistakes and make the code hard to maintain.

This topic looks solved anyway by the lack of responses from the author.
 
Status
Not open for further replies.
Top