Few clarifications on recursion

[Panagiotis Atmatzidis]

Hello,

I'm following C. Pine's manual for a smooth intro into ruby & =
programming. I'm just curious about this exercise which should teach =
recursion.
Here is the program sample, which as you can see is a simple factorial =
calculator:

def factorial num
if num < 0
return 'You can\'t take the factoria of a negative number'
end

if num <=3D 1
1
else
num * factorial(num-1)
end
end


Although it introduces many interesting concepts to me (i. e. I did not =
knew that after the "if" statement a single _1_ with no quotes could be =
used) I fail to see how the num changes value. The way I read the code =
here:

num * factorial(num-1)

is 30*29 for "puts factorial(30)" not 30*29*28... which is how it works. =
I've tested the code works fine.

The book although, in my opinion is excellent (so far) for starters, =
does not explain - or it does but I did not understand it nevertheless - =
how this piece of code works.

regards

Panagiotis (atmosx) Atmatzidis

email: (e-mail address removed)
URL: http://www.convalesco.org
GnuPG ID: 0xFC4E8BB4=20
gpg --keyserver x-hkp://pgp.mit.edu --recv-keys 0xFC4E8BB4

 

[Fleck Jean-Julien]

Hello Panagiotis,

is 30*29 for "puts factorial(30)" not 30*29*28... which is how it works. =

I've tested the code works fine.

The book although, in my opinion is excellent (so far) for starters, does=

not explain - or it does but I did not understand it nevertheless - how th=
is piece of code works.

Well, it is exactly like a mathematical recursion. First, you need the
initialisation:

factorial(0) =3D 1 which is what 0! should be equal.

Then you suppose, for n>=3D0, that you have factorial(n-1) =3D (n-1)!
thus, factorial(n) returns n * factorial(n-1) =3D n * (n-1)! =3D n!

Programaticaly, I suppose each call to factorial waits for the next
one to finish, which occurs only when you ask for factorial(0).
Thus, when you ask for factorial(30), there are 30 method calls
waiting for factorial(0) to return, which allows factorial(1) to
return, which allows factorial(2) to return... etc. until
factorial(30) returns.

Hope this helps,

--=20
JJ Fleck
PCSI1 Lyc=E9e Kl=E9ber

 

[Josh Cheek]

[Note: parts of this message were removed to make it a legal post.]

Although it introduces many interesting concepts to me (i. e. I did not
knew that after the "if" statement a single _1_ with no quotes could be
used) I fail to see how the num changes value. The way I read the code here:

In Ruby, the last line of a function is returned. In this case, the last
line is the if statement. The if statement evaluates to the last line of
code inside of it. This means that if the number is less than or equal to 1,
the last line of the if statement will be 1, so that is what the if
statement will evaluate to, and thus that is what the function will return.

num * factorial(num-1)

is 30*29 for "puts factorial(30)" not 30*29*28... which is how it works.
I've tested the code works fine.

This is the recursive portion, it is not 30*29, it is 30*factorial(29), and
factorial(29) is 29*factorial(28) and factorial(28) is 28*factorial(27)
etcetera until you get to 1, and factorial(1) is just 1, because it is less
than or equal to 1.

If you expand these calls out, you get 30*( 28*( 27*( ... *(1) ) ) )


If you are still confused by this, try going the other way. Start with 1,
and go up. If factorial(1) returns 1, what will factorial(2) return (go
through the code)? And then what will factorial(3) return? And so on.

 

[Phillip Gawlowski]

Although it introduces many interesting concepts to me (i. e. I did not knew that after the "if" statement a single _1_ with no quotes could be used) I fail to see how the num changes value. The way I read the code here:

num * factorial(num-1)

is 30*29 for "puts factorial(30)" not 30*29*28... which is how it works. I've tested the code works fine.

The book although, in my opinion is excellent (so far) for starters, does not explain - or it does but I did not understand it nevertheless - how this piece of code works.

In a nutshell, recursion means performing the same action until a
condition is met.

In your case, factorial does "num * (num - 1)" until num is 1 (or
smaller than one). It then gives you the result.

You can test this with:

def factorial num
if num < 0
puts "You can't take the factoria of a negative number"
end

puts "num is: #{num}" # this prints our the value of num before each
# recursion

if num <= 1
1
else
num * factorial(num-1)
end

end

puts factorial 30

I hope that clears up your confusing about recursion? (If that *was*
where you were confused..)

 

[Panagiotis Atmatzidis]

Hello

In Ruby, the last line of a function is returned. In this case, the = last
line is the if statement. The if statement evaluates to the last line = of
code inside of it. This means that if the number is less than or equal = to 1,
the last line of the if statement will be 1, so that is what the if
statement will evaluate to, and thus that is what the function will =

return.

Okay returns the last statement, but is it a number or a string?

=20
=20
This is the recursive portion, it is not 30*29, it is = 30*factorial(29), and
factorial(29) is 29*factorial(28) and factorial(28) is = 28*factorial(27)
etcetera until you get to 1, and factorial(1) is just 1, because it is = less
than or equal to 1.
=20
If you expand these calls out, you get 30*( 28*( 27*( ... *(1) ) ) )
=20
=20
If you are still confused by this, try going the other way. Start with = 1,
and go up. If factorial(1) returns 1, what will factorial(2) return = (go
through the code)? And then what will factorial(3) return? And so on.

Yes you are right. Now I get it. Thank you for pointing this out for =
nicely!

So this is the whole point of recursion to run the program (backwards in =
this case) until the even that will stop the recursion happens.

Thanks to all & regards

Panagiotis (atmosx) Atmatzidis

email: (e-mail address removed)
URL: http://www.convalesco.org
GnuPG ID: 0xFC4E8BB4=20
gpg --keyserver x-hkp://pgp.mit.edu --recv-keys 0xFC4E8BB4

 

[Phillip Gawlowski]

Okay returns the last statement, but is it a number or a string?

Depends on what was thrown into it, and what was done to it in the
process.

In your case, it's a number.

A neat way to test this is capturing the output of a function in a
variable, and do a
puts variable.class
which prints the Class of the variable (everything's an Object in Ruby,
and thus has a class, more or less).

For example:
puts Array.new.class
puts [].class
puts "string".class
puts 1.class
puts 1.0.class # Ruby knows you are using a Float here
puts Class.class

etc. pp.

 

[Robert Klemme]

In a nutshell, recursion means performing the same action until a
condition is met.

Actually that description is true for loops (aka iterations) as well.
The important bit of recursion - and the part where recursion and
iteration differ - in programming languages is, that it needs a
_function (or method)_ which calls _itself_. Most of the time it
happens directly (as in this example) but it may as well happen
indirectly (f calls g, g calls f) although I cannot think of a
reasonable example right now. (Most indirect recursions are probably
programming errors which you notice when a SystemStackError pops up. )

Certain forms of recursion can actually be transformed into iterations
(which some programming languages / runtimes actually do). That way you
usually get better performance. See
http://en.wikipedia.org/wiki/Tail_recursion

Kind regards

robert

 

[Phillip Gawlowski]

Actually that description is true for loops (aka iterations) as well.
The important bit of recursion - and the part where recursion and
iteration differ - in programming languages is, that it needs a
_function (or method)_ which calls _itself_.

The actual difference is: recursion gives me headaches, iteration
doesn't. ;P

 

[Brian Candler]

The actual difference is: recursion gives me headaches, iteration
doesn't. ;P

But while this particular example is one which can easily be written
either iteratively or recursively, there are many problems which are
easy to solve recursively but more difficult to do iteratively.

Consider for example the classic "Towers of Hanoi" problem:

-|- | |
--|-- | |
---|--- | |
----|---- | |
A B C

Tower A is a stack of discs of decreasing size (I've shown 4; more often
it's seen with 8 but I couldn't be bothered to drawn them

The problem is to move all the discs from A to B. However the rules are:
- you can move only one disc at a time
- each disc after being lifted from one tower must be put down onto one
of the other towers (A, B or C)
- you cannot put a larger disc on top of a smaller one

The recursive solution is simple: to move N discs from tower A to tower
B, move N-1 discs from tower A to tower C, then move one disc from A to
B, then move N-1 discs from tower C to tower B. The case of moving 0
discs is trivial, and the rest just falls out.

This can be written in a handful of lines of code. You don't even need
to maintain a data structure to record where the discs are(*). You'll
find it needs 2^N moves to move a tower of height N.

(*) Although if you do, you can display the whole state at each point.

 

[Bob Hutchison]

Hi,

So this is the whole point of recursion to run the program
(backwards in this case) until the even that will stop the recursion
happens.

If are interested in pursuing recursion in any depth, you are in luck:

<http://se.inf.ethz.ch/people/meyer/down/touch/index.html>

The sample chapter is on recursion, and does a good job of explaining
recursion I think (and checkout my email address It is using
Eiffel rather than Ruby, but that won't matter since the ideas are
directly transferable.

Cheers,
Bob