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 3029 for “puts factorial(30)” not 3029*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.
is 3029 for “puts factorial(30)” not 3029*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.
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 3029 for “puts factorial(30)” not 3029*28… which is how it works.
I’ve tested the code works fine.
This is the recursive portion, it is not 3029, it is 30factorial(29),
and
factorial(29) is 29factorial(28) and factorial(28) is 28factorial(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.
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 3029 for “puts factorial(30)” not 3029*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…)
Hello
On 03 Ιαν 2010, at 6:46 μ.μ., Josh C. wrote:
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?
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.
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
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
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.
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.
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.
The important bit of recursion - and the part where recursion and
The important bit of recursion - and the part where recursion and