Recursion WTF!

Hello friends, my mind is blowing up in flames. I can't understand how
recursion works in this certainly case( this is part of 'Learn to
program' of Chris Pine ):

M = 'land'
o = 'water'

world = [
[o,o,o,o,o,M,o,o,o,o,o],
[o,o,o,o,M,M,o,o,o,o,o],
[o,o,o,o,o,M,o,o,M,M,o],
[o,o,o,M,o,M,o,o,o,M,o],
[o,o,o,o,o,M,M,o,o,o,o],
[o,o,o,o,M,M,M,M,o,o,o],
[M,M,M,M,M,M,M,M,M,M,M],
[o,o,o,M,M,o,M,M,M,o,o],
[o,o,o,o,o,o,M,M,o,o,o],
[o,M,o,o,o,M,M,o,o,o,o],
[o,o,o,o,o,M,o,o,o,o,o]]

def continent_size world, x ,y

if x < 0 or x > 10 or y < 0 or y > 10
return 0
end

if world[y][x] != 'land'
return 0
end

size = 1
world [y][x] = 'counted land'

size = size + continent_size(world, x-1, y-1)
size = size + continent_size(world, x , y-1)
size = size + continent_size(world, x+1, y-1)
size = size + continent_size(world, x-1, y )
size = size + continent_size(world, x+1, y )
size = size + continent_size(world, x-1, y+1)
size = size + continent_size(world, x , y+1)
size = size + continent_size(world, x+1, y+1)
size

end

puts continent_size(world, 5, 5)
#result is 32

I can't figure out how the program "counts" the M's, can't understand
in what part size = size + a_number( guess it must be 1(?). I guess this
is not easy to explain, by the way if you can give me a hand I'll take
it! Thanks for your time.

···

--
Posted via http://www.ruby-forum.com/.

First, understand that M and o are objects which have the string
values 'land' and 'water', respectively. The method actually counts
elements according to whether they equal 'land' or not; anything that
equals 'land' is also equal to M.

···

2011/10/31 Damián M. González <gonzalezdamianm@hotmail.com>:

I can't figure out how the program "counts" the M's, can't understand
in what part size = size + a_number( guess it must be 1(?). I guess this
is not easy to explain, by the way if you can give me a hand I'll take
it! Thanks for your time.

Where recursion is concerned, it's often best to use the debugger and begin stepping through the code until the pattern becomes clear. In your case, an even better way may be to visualize your map at every step. If you run the code with minor adjustments you can create a nice output at ever step. For example:

Looking at tile (5,5)
oooooMooooo
ooooMMooooo
oooooMooMMo
oooMoMoooMo
oooooMMoooo
ooooMMMMooo
MMMMMMMMMMM
oooMMoMMMoo
ooooooMMooo
oMoooMMoooo
oooooMooooo

Looking at tile (4,4)
oooooMooooo
ooooMMooooo
oooooMooMMo
oooMoMoooMo
oooooMMoooo
ooooMXMMooo
MMMMMMMMMMM
oooMMoMMMoo
ooooooMMooo
oMoooMMoooo
oooooMooooo

Looking at tile (5,4)
oooooMooooo
ooooMMooooo
oooooMooMMo
oooMoMoooMo
oooooMMoooo
ooooMXMMooo
MMMMMMMMMMM
oooMMoMMMoo
ooooooMMooo
oMoooMMoooo
oooooMooooo

. . . and so on. I've pasted the code you can run to produce the output here:

Hope that helps!

Sylvester

···

On Oct 31, 2011, at 11:11 PM, Damián M. González wrote:

Hello friends, my mind is blowing up in flames. I can't understand how
recursion works in this certainly case( this is part of 'Learn to
program' of Chris Pine ):

M = 'land'
o = 'water'

world = [
[o,o,o,o,o,M,o,o,o,o,o],
[o,o,o,o,M,M,o,o,o,o,o],
[o,o,o,o,o,M,o,o,M,M,o],
[o,o,o,M,o,M,o,o,o,M,o],
[o,o,o,o,o,M,M,o,o,o,o],
[o,o,o,o,M,M,M,M,o,o,o],
[M,M,M,M,M,M,M,M,M,M,M],
[o,o,o,M,M,o,M,M,M,o,o],
[o,o,o,o,o,o,M,M,o,o,o],
[o,M,o,o,o,M,M,o,o,o,o],
[o,o,o,o,o,M,o,o,o,o,o]]

def continent_size world, x ,y

if x < 0 or x > 10 or y < 0 or y > 10
return 0
end

if world[y] != 'land'
return 0
end

size = 1
world [y] = 'counted land'

size = size + continent_size(world, x-1, y-1)
size = size + continent_size(world, x , y-1)
size = size + continent_size(world, x+1, y-1)
size = size + continent_size(world, x-1, y )
size = size + continent_size(world, x+1, y )
size = size + continent_size(world, x-1, y+1)
size = size + continent_size(world, x , y+1)
size = size + continent_size(world, x+1, y+1)
size

end

puts continent_size(world, 5, 5)
#result is 32

I can't figure out how the program "counts" the M's, can't understand
in what part size = size + a_number( guess it must be 1(?). I guess this
is not easy to explain, by the way if you can give me a hand I'll take
it! Thanks for your time.

I have a video to introduce people to recursion that you might find
helpful. It's about 20 minutes.
http://ruby-kickstart.com/#session-recursion

···

2011/10/31 Damián M. González <gonzalezdamianm@hotmail.com>

Hello friends, my mind is blowing up in flames. I can't understand how
recursion works in this certainly case( this is part of 'Learn to
program' of Chris Pine ):

Thank Eric and Sylvester for answer. :slight_smile:

Great job Sylvester! that help me a lot, but still i was very confused.
We have to admit, that understand that source code is not easy for a
noob. But, the fact that it burn your mind make you learn, that's why I
never feel dissapoint in this cases, because I'm learning. So I keep
going over and over on the book and pencils and keyboard... I get it!!
Haha! yes. I had to see step by step by step by step and got it. I don't
have a camera to take a picture of the manuscripts that i did trying to
figure out how this work, LOL is a big one. Cheers!

···

--
Posted via http://www.ruby-forum.com/.

To understand recursion, you must first understand recursion. :wink:

···

--
LOOKING FOR WORK! What: Ruby (on/off Rails), Python, other modern languages.
Where: Northern Virginia, Washington DC (near Orange Line), and remote work.
See: davearonson.com (main) * codosaur.us (code) * dare2xl.com (excellence).
Specialization is for insects. (Heinlein) - Have Pun, Will Babble! (Aronson)

Posted by Josh Cheek (josh-cheek) on 2011-11-02 17:07

I have a video to introduce people to recursion that you might find
helpful. It's about 20 minutes.
http://ruby-kickstart.com/#session-recursion

Wow, that's an amazing page, and I very like the introduction. All what
Ruby was doing on me is: joy, and that`s your introduction do: encourage
the people to enjoy this beautifull programing language. I`ll watch all
your tutorials, I know that will help me, thanks.

Posted by Sam Rose (Guest) on 2011-11-03 05:33

I hope my favourite example furthered your understanding instead of
confusing you :slight_smile:

Ey Sam! Yes, i got it from the beginning and is a very good
example...seems that I`m starting to see how work`s through the water.
That`s help me a lot, thank you for your time.

···

--
Posted via http://www.ruby-forum.com/\.

Recursion is a really great tool for problems like this :slight_smile: I think the
example is a little bit contrived, though. Counting the land tiles is
nothing that a simple loop or two couldn't solve. However, I suppose
he is trying to illustrate a point.

I know you said you understand it, but one of my favourite examples of
recursion is this (somewhat inefficient) Fibonacci sequence generator:

def fib n
  if n <= 0
return 1
  else
return fib(n - 2) + fib(n - 1)
  end
end

If you ran this code:

(1..10).each do |i|
puts fib(i)
end

The output would be:

2
3
5
8
13
21
34
55
89
144

(It doesn't start quite at the start of the sequence but if you really
wanted it to, I'm sure you could tweak it to your liking)

The reason this works is because of the "base case", namely if n <= 0,
return 1. Because of that, the recursive loop has an end to it and
will unwind to give the correct answer :slight_smile:

I hope my favourite example furthered your understanding instead of
confusing you :slight_smile:

···

On 2 November 2011 10:49, Sam Rose <samwho@lbak.co.uk> wrote:

Recursion is a really great tool for problems like this :slight_smile: I think the
example is a little bit contrived. This is nothing that a simple loop
or two couldn't solve.

I know you said you understand it, but one of my favourite examples of
recursion is this (somewhat inefficient) fibonacci sequence generator:

def fib n
if n <= 0
return 1
else
return fib(n - 2) + fib(n - 1)
end
end

If you wrote this code:

(1..10).each do |i|
puts fib(i)
end

The output would be:

2
3
5
8
13
21
34
55
89
144

The reason is works is because of the "base case", namely if n <= 0,
return 1. Because of that, the recursive loop has an end to it and
will unwind to give the correct answer :slight_smile:

I hope my favourite example furthered your understanding instead of
confusing you further :slight_smile:

2011/11/1 Damián M. González <gonzalezdamianm@hotmail.com>:

Thank Eric and Sylvester for answer. :slight_smile:

Great job Sylvester! that help me a lot, but still i was very confused.
We have to admit, that understand that source code is not easy for a
noob. But, the fact that it burn your mind make you learn, that's why I
never feel dissapoint in this cases, because I'm learning. So I keep
going over and over on the book and pencils and keyboard... I get it!!
Haha! yes. I had to see step by step by step by step and got it. I don't
have a camera to take a picture of the manuscripts that i did trying to
figure out how this work, LOL is a big one. Cheers!

--
Posted via http://www.ruby-forum.com/\.

I think its not about counting all land tiles, instead it counts
connected land tiles (containing the start point).
This problem isn't so easy to solve with a simple loop.

···

2011/11/2 Sam Rose <samwho@lbak.co.uk>:

Recursion is a really great tool for problems like this :slight_smile: I think the
example is a little bit contrived, though. Counting the land tiles is
nothing that a simple loop or two couldn't solve. However, I suppose
he is trying to illustrate a point.

Ah, right! Sorry, I misunderstood.

Yeah, you're absolutely right. Counting connected land tiles would be
really hard to do just using loops. I remember using a similar
recursive algorithm to this one when writing a Minesweeper game :slight_smile:

Sorry, I thought it was just counting all land tiles.

···

On 3 November 2011 21:59, Gunther Diemant <g.diemant@gmx.net> wrote:

2011/11/2 Sam Rose <samwho@lbak.co.uk>:

Recursion is a really great tool for problems like this :slight_smile: I think the
example is a little bit contrived, though. Counting the land tiles is
nothing that a simple loop or two couldn't solve. However, I suppose
he is trying to illustrate a point.

I think its not about counting all land tiles, instead it counts
connected land tiles (containing the start point).
This problem isn't so easy to solve with a simple loop.