Offline
since two weeks I had lessons on recursion in JavaBlock and I still don't understand it.
Can someone explain this to me? And an example in Lua.
Thanks
Forum
Off Topic Recursion
Recursion
11 replies
1 
since two weeks I had lessons on recursion in JavaBlock and I still don't understand it.
Can someone explain this to me? And an example in Lua.
Thanks
1
2
3
4
5
6
7
2
3
4
5
6
7
function fac(x){
if x == 0 then {
return 1;
} else {
return x*fac(x-1)
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
function add(x){
/* Static Part */
/* 1 = 1 */
if ( x == 1 ) {
return 1;
}
/* Recursive Part */
else{
return ( x + add(x-1) );
}
}
So only use recursion if you're sure that it won't recurse too often and if the performance of your code isn't very important.
It might be good for theory and to explain what code does but it's bad in practice. At least when using imperative languages like Lua.
DC has writtenNote that recursion is a bad idea in code which is actually used and performance-critical. Function calls are much more expensive than regular loops.
Most non-interpreted ( and some that are interpreted ) programming languages have optimisations that deal with tail-recursive functions, I believe it is in clang's -O1 or -O2 flags, which would speak for GCC as well.
DC has writtenAt least when using imperative languages like Lua.
For the standard Lua VM implementation hosted at lua.org this stands true. LuaJIT does tail-recursion optimisation.
@
AlcatrazZ: Recursion is when a subroutine or function calls itself, such as this:
1
2
3
4
5
6
2
3
4
5
6
function recursive_function(x) print(x) if( x > 1 ) then recursive_function(x-1) end end
Remember always that no amount of people explaining things will make programming concepts easy. What you should do is get a basic understanding and then try and find cases in which you can use them, this will further your understanding and also the practice will help other areas in your learning.
If you are feeling boss and want to see a practical use of recursion, look here:
You have a 51x51 labyrinth. You only have one entrance/exit (1,0). Then, the program must start "digging" the labyrinth by moving only two blocks ahead each time in a random direction. You cannot dig the external walls and you cannot dig in order to cause a junction ( 3 or more 'roads' meet ).
This is an excellent example on where recursion is required..
So, I was had the program in the school:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
function factorial(x)
if x == 0 then
wynik = 1
print("x3: "..x)
else
print("x: "..x)
wynik = x * factorial(x - 1)
print("x2: "..x)
end
print("return "..wynik)
return wynik
end
print(factorial(5))
Output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
x: 5 x: 4 x: 3 x: 2 x: 1 x3: 0 return 1 x2: 1 return 1 x2: 2 return 2 x2: 3 return 6 x2: 4 return 24 x2: 5 return 120 120
Return function should go end, but the script is always running.
edited 4×, last 12.04.14 02:44:04 pm
AlcatrazZ:That's a pretty poorly written version of the factorial function. It's using a global variable, usually not so great an idea when doing recursive programming. Read
ohaz's example for a better 'factorial' function.Also, what do you mean by 'the script is always running'? If it isn't ending, then your stopping condition is miffed. Probably best to just rewrite the code given it is so tiny. You do know what the factorial of an integer is, right?
DannyDeth: AlcatrazZ has writtenI don't know how it above 7 line, it is possible.
As for me, this code should have 7 lines, not 18.
I don't know how this function returns back to the program with already returned value 1 (line 7).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
function factorial(x)
if x == 0 then
wynik = 1
print("x3: "..x) -- this print will be called once, when x is 0
else
print("x: "..x) -- this will be called for x=5 to 1, 5 times
wynik = x * factorial(x - 1)
print("x2: "..x) -- this will be called for x=5 to 1, 5 times
end
print("return "..wynik) -- this will be called from 5 to 0, 6 times
return wynik
end
print(factorial(5)) -- this will be called once
1 + 5 + 5 + 6 + 1 = 18 print calls.
It's too difficult for me at the moment.
1