Forum

> > Off Topic > Recursion
Forums overviewOff Topic overviewLog in to reply

English Recursion

11 replies
To the start Previous 1 Next To the start

old Recursion

AlcatrazZ
BANNED Off Offline

Quote
Hello,
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

old Re: Recursion

ohaz
User Off Offline

Quote
This recursive function returns the factorial of a number x (the factorial of a number x is x*(x-1)*(x-2)*(x-3)*...
1
2
3
4
5
6
7
function fac(x){
  if x == 0 then {
     return 1;
  } else {
     return x*fac(x-1)
  }
}
The important thing about recursive functions is that they call themselves.

old Re: Recursion

sixpack
User Off Offline

Quote
A recursive function has two parts. The first one is the static, and the second is the recursive one. For example, if you want a function that adds all numbers from 1 to x you could do this:

1
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) );
    }
}

old Re: Recursion

DC
Admin Off Offline

Quote
Note that recursion is a bad idea in code which is actually used and performance-critical. Function calls are much more expensive than regular loops. Also having too many function calls in a recursive function can lead to a stack overflow (the stack keeps track of nested function calls) which is a critical error and ends the execution of your program/script.

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.

old Re: Recursion

DannyDeth
User Off Offline

Quote
user DC has written
Note 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.

user DC has written
At 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.

@user AlcatrazZ:
Recursion is when a subroutine or function calls itself, such as this:
1
2
3
4
5
6
function recursive_function(x)
	print(x)
	if( x > 1 ) then
		recursive_function(x-1)
	end
end
When writing recursive functions, you should always have some input state that will stop the recursion ( in the case I have provided, it is when x is no longer greater than 1 ), otherwise a stack overflow will happen. Lua is a stack-based language ( most [imperative..?] programming languages are ). A conceptualisation of the stack would be when a function is called, the code pushes a "returning jump" position into the stack, so that when the function called has done what is needed, the program can jump back to carry on with the code after that function call. If your function never stops calling itself, it will push so many returning jumps onto that stack that the stack runs out of space to put it, which is called a stack overflow.

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:
Recursion used in practice >

old Re: Recursion

sixpack
User Off Offline

Quote
If you already know about the use of tables, here's a cool exercise:

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..

old Recursion

AlcatrazZ
BANNED Off Offline

Quote
Oh
So, I was had the program in the school:
1
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))
The print functions is added by meself.

Output:
1
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
I don't know how it above 7 line, it is possible.
Return function should go end, but the script is always running.
edited 4×, last 12.04.14 02:44:04 pm

old Re: Recursion

DannyDeth
User Off Offline

Quote
@user 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 user 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?

old Re: Recursion

AlcatrazZ
BANNED Off Offline

Quote
@user DannyDeth:
user AlcatrazZ has written
I don't know how it above 7 line, it is possible.

Output >

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).

old Re: Recursion

DannyDeth
User Off Offline

Quote
It's quite easy to see why the output is 18 lines long:
1
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.

old Re: Recursion

AlcatrazZ
BANNED Off Offline

Quote
Recursion really fu***ng my brain.
It's too difficult for me at the moment.

old Re: Recursion

DannyDeth
User Off Offline

Quote
The problem you have here is poorly written code. There isn't much to understand about recursion other than that recursion is when a function calls itself.
To the start Previous 1 Next To the start
Log in to replyOff Topic overviewForums overview