Recursion WTF!

Ruby
1

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

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.

2

On Oct 31, 2011, at 11:11 PM, Damin M. Gonzlez wrote:

[o,o,o,o,o,M,o,o,M,M,o],

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.

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

3

2011/10/31 Damin M. Gonzlez [email protected]:

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.

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.

4

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!

5

2011/10/31 Damin M. Gonzlez [email protected]

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

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

6

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:

7

Posted by Josh C. (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 thats your introduction do: encourage the people to enjoy this beautifull programing language. Ill watch all
your tutorials, I know that will help me, thanks.

Posted by Sam R. (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 Im starting to see how works through the water.
That`s help me a lot, thank you for your time.

8

2011/11/2 Sam R. [email protected]:

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.

9

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.

10

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