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 <= 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: atma@convalesco.org
URL: http://www.convalesco.org
GnuPG ID: 0xFC4E8BB4
gpg --keyserver x-hkp://pgp.mit.edu --recv-keys 0xFC4E8BB4
···
--
The wise man said: "Never argue with an idiot. They bring you down to their level and beat you with experience."
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 this piece of code works.
Well, it is exactly like a mathematical recursion. First, you need the
initialisation:
factorial(0) = 1 which is what 0! should be equal.
Then you suppose, for n>=0, that you have factorial(n-1) = (n-1)!
thus, factorial(n) returns n * factorial(n-1) = n * (n-1)! = 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,
···
--
JJ Fleck
PCSI1 Lycée Kléber
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.
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..)
···
On 03.01.2010 17:16, Panagiotis Atmatzidis wrote:
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.
--
Phillip Gawlowski
Hello
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.
Okay returns the last statement, but is it a number or a string?
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.
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: atma@convalesco.org
URL: http://www.convalesco.org
GnuPG ID: 0xFC4E8BB4
gpg --keyserver x-hkp://pgp.mit.edu --recv-keys 0xFC4E8BB4
···
On 03 Ιαν 2010, at 6:46 μ.μ., Josh Cheek wrote:
--
The wise man said: "Never argue with an idiot. They bring you down to their level and beat you with experience."
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 Tail call - Wikipedia
Kind regards
robert
···
On 01/03/2010 05:52 PM, Phillip Gawlowski wrote:
On 03.01.2010 17:16, Panagiotis Atmatzidis wrote:
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.
--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/
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.
···
On 03.01.2010 17:53, Panagiotis Atmatzidis wrote:
Okay returns the last statement, but is it a number or a string?
The actual difference is: recursion gives me headaches, iteration doesn't. 
···
On 03.01.2010 18:25, Robert Klemme wrote:
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_.
--
Phillip Gawlowski
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
···
On 3-Jan-10, at 11:53 AM, Panagiotis Atmatzidis wrote:
----
Bob Hutchison
Recursive Design Inc.
http://www.recursive.ca/
weblog: http://xampl.com/so
Phillip Gawlowski wrote:
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.
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.
···
--
Posted via http://www.ruby-forum.com/\.