Need help understanding recursion

Ruby
1

Ive been reading Chris P.'s book ‘Learn to Program’ and its been going
great up until I got to chapter 10 on recursion and thus has completely
taken all my excitement from going forward. I understand that recursion
is a method that will continue to call itself till there is an attribute
to cause it to exit the loop. The example in the book though has me all
sorts of confused. Can someone walk me through the example and bring
back the excitement to continue to learn Ruby!

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)

2

pedro oliva [email protected] wrote:

M = ‘land’
[o,o,o,M,M,o,M,M,M,o,o],
if world[y][x] != ‘land’
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)

What I would suggest is installing pry and using it to step through your
program.

If it’s basic understanding of recursion that’s lacking right now,
perhaps a simpler example might do as well. The most common introduction
to a recursive function is the factorial function, which is nominally
defined as:

n is a postive integer
n! == n * (n-1) … * 1

so:

def factorial(n)
raise “#{n} is not a postive integer!” unless (n.is_a?(Integer) && n >
0)
return 1 if n == 1 # this is the stopping condition
n * factorial(n-1) # this calculates the factorial
end

2.0.0p195 :006 > factorial(1)
=> 1
2.0.0p195 :007 > factorial(2)
=> 2
2.0.0p195 :008 > factorial(10)
=> 3628800
2.0.0p195 :009 > factorial(0)
RuntimeError: 0 is not a positive Integer
2.0.0p195 :010 > factorial(-10)
RuntimeError: -10 is not a positive Integer
2.0.0p195 :011 > factorial(‘a’)
RuntimeError: a is not a positive Integer
2.0.0p195 :012 > factorial(nil)
RuntimeError: is not a positive Integer

2.0.0p195 :014 > (1…10).inject([]){|memo, obj| memo << factorial(obj)}
=> [1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]

Another beginner recursive example is the Fibonacci sequence (0, 1, 1,
2, 3, 5, …)

def fibonacci(n)
raise “#{n} is not a non-negative Integer” unless (n.is_a?(Integer) &&
n >= 0)
return 0 if n == 0
return 1 if n == 1
fibonacci(n-1)+fibonacci(n-2)
end

2.0.0p195 :037 > (0…10).reduce([]){|m,o| m << fibonacci(o)}
=> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

I’ve tossed these up on a couple of simple recursion examples · GitHub

Stick with Ruby! It’s great!

3

Subject: Need help understanding recursion.
Date: gio 06 giu 13 09:19:47 +0900

Quoting pedro oliva ([email protected]):

The example in the book though has me all sorts of confused. Can
someone walk me through the example and bring back the excitement to
continue to learn Ruby!

The example is well-thought-out and well-written. What is it that you
do not understand? It is probably better (if you care for the
excitement - and you should), for you to take the time to put down in
words the circumstances of your confusion. It may even be that, thanks
to the exercise, the confusion will dissipate all by itself!

Carlo

4

Read through ‘The Little Schemer’ and recursion will be a step by step
process.

5

Recursive algorithms are essentially self-calling algorithms – so any
method that calls itself is recursive. Typically you’ll see the
self-calling section in the return statement. In ruby that would be the
last line of the method before the final end statement. Also, all
recursive methods have a base case, the condition that tells the method
when to exit.

The benefits are sometimes performance gains, lower space complexity,
and more elegant written code (though that’s up for you to decide).
Mathematicians more often consider recursive methods more elegant, where
typically the non-math oriented prefer iterative methods for some
reason. Though one way isn’t necessarily better than the other.

I think what would help you is to see examples of recursive methods
compared directly to their iterative counterparts, and compare their
running speeds. The fibonacci algorithm is one of the most popular
examples used. Read more about the specific sequence here:

Below are two versions that calculate the nth number in the fibonacci
sequence:

iterative

def fibIter(n)
return 0 if n == 0
fibPrev, fib = 1, 1
(n.abs - 2).times { fibPrev, fib = fib, fib + fibPrev }
fib * (n<0 ? (-1)**(n+1) : 1)
end

recursive

def fibRec(n)
if n <= -2
(-1)**(n+1) * fibRec(n.abs)
elsif n <= 1
n.abs
else
fibRec(n-1) + fibRec(n-2)
end
end

If you benchmark these, you’ll notice the iterative method typically
performs better than the recursive one.

require ‘benchmark’

Benchmark.bm do |x|
x.report(“fibIter 10”) { fibIter(10) }
x.report(“fibRec 10”) { fibRec(10) }
x.report(“fibIter 30”) { fibIter(30) }
x.report(“fibRec 30”) { fibRec(30) }
end
user system total real
fibIter 0.000000 0.000000 0.000000 ( 0.000014)
fibRec 0.000000 0.000000 0.000000 ( 0.000032)
fibIter 0.000000 0.000000 0.000000 ( 0.000013)
fibRec 0.340000 0.000000 0.340000 ( 0.350754)

So in this case, the iterative method is faster than the recursive
counter part.

Let me show you an example where a recursive method is much faster.
Below are two sorting algorithms, bubble sort and quick sort. Bubble
sort is a iterative sorting algorithm and quick sort is a recursive
sorting algorithm.

class Array
def bubblesort
length.times do |j|
for i in 1…(length - j)
if self[i] < self[i - 1]
self[i], self[i - 1] = self[i - 1], self[i]
end
end
end
self
end

def quick_sort
return self if length <= 1
pivot = self[length / 2]
find_all { |i| i < pivot }.quick_sort +
find_all { |i| i == pivot } +
find_all { |i| i > pivot }.quick_sort
end
end

ary =
[0,1,4,5,6,7,8,9,12,26,45,67,78,90,98,123,211,234,456,769,865,2345,3215,14345,24324]
ary.shuffle!

Benchmark.bm do |x|
x.report(“bubble sort”) { ary.bubblesort }
ary.shuffle!
x.report(“quick sort”) { ary.quick_sort }
end

   user     system      total        real

bubble sort 0.000000 0.000000 0.000000 ( 0.000165)
quick sort 0.000000 0.000000 0.000000 ( 0.000096)

As you can see in the benchmarking test, quicksort typically works in
half the time of bubble sort. At worst, quicksort will always sort at
nlog(n) times, where n is the number of array elements (In CS
terminology this is called big O nlog(n) time). A exhaustive iterative
method, such as bubble sort, has a worst case of n^2 time.

Here’s an animation written in javascript that illustrates the
differences very well visually:
http://liamks.github.io/Sorting-Visualization/

An important example of a recursive algorithm improving performance is
the binary search algorithm. This algorithm greatly improve searching
speeds in sorted arrays. A linear search will always work in 0(n) time,
whereas a binary search at worst works in O(log(n)) time.

class Array
def binary_search(val, low=0, high=(length - 1))
return nil if high < low
mid = (low + high) / 2
case
when self[mid] > val then binary_search(val, low, mid-1)
when self[mid] < val then binary_search(val, mid+1, high)
else mid
end
end
end

As you can see from the examples above, recursive methods sometimes
improve performance speeds (binary search & sorting) and sometimes don’t
(fibonacci). One isn’t necessarily better than the other, but they do
offer stylistic differences, which would be important to a rubyist.
Performance gains are not typically important in scripting languages,
but it becomes important in lower level languages like C, C++, Java, and
Go. Where ever running times become important, you should really
understand recursion.

Recursion is even more important in purely functionally programming
languages like Scheme, Lisp, and Haskell. Ruby, as an applied functional
and scripting programming language, has too many performance issues to
make all recursive techniques practical.

Some languages are capable of performing tail recursion, which is a type
of recursive technique that involves using an accumulator variable to
reduce building up a large recursive stack. Tail recursive methods often
have huge performance gains, but not all environments support it
currently:
(java - Why does the JVM still not support tail-call optimization? - Stack Overflow)
Though, it’s been such a major issue for a long time, I’m certain it’ll
become available in the future.

Id say, take it easy. Maybe Chris P. is using a bad starter example. I
struggled with recursion when I had to first learn it, most do, but it
is a
really nice alternative way of writing eloquent
code – and after you’ve master it you’ll feel a very strong
appreciation for recursive solutions and those that understand it. It
will also help you understand more advanced CS topics in the future.
Functional/recursive programming techniques are leading the way in both
industry and academia – so it would be of a huge advantage to
understand it.

Sorry for the long post. I hope this helped.

6

Brandon W. [email protected] wrote:

Read through ‘The Little Schemer’ and recursion will be a step by step process.

Oh, well played, Brandon, well played. :slight_smile:

7

Sorry, I realized that I should probably help you understand your
example as well.

M = ‘land’
o = ‘water’

So world is a 2d array, where M equals land and o equals water. The x

axis goes from left to right, and the y axis going from top to bottom.
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]]

continent_size takes in the 2d array, and a beginning coordinate on

the map (x, y).
def continent_size world, x ,y

if current x or y is greater than 10 (10 would be beyond the bounds

of the array map) or less than 0 (there are no negative coordinates in
this example), then it returns 0.
if x < 0 or x > 10 or y < 0 or y > 10
return 0 # This condition(base-case) represents the bounds of the
map.
end

if current coordinate is not equal to land than it returns 0.

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

size = 1 # each coordinate equals 1 unit of measure.
world [y][x] = ‘counted land’ # after a coordinate is visited it is
marked with ‘counted land’ so the method doesn’t read the same
coordinate twice.

after marking the current coordinate with ‘counted land’ the method

calls itself on all adjacent coordinates. Adding 1 to size, marking a
coordinate that is land with ‘counted land’ if land is found, or adding
0 if ‘water’/o is discovered. If ‘counted land’, ‘water’, or the bounds
of the map are discovered this is where the method terminates. If ‘land’
is discovered, then it continues on to the other adjacent coordinates.
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 # this is what is returned.

end

puts continent_size(world, 5, 5)

So what you get is the size of a land mass on the 10x10 map. Try

putting continent_size(world, 9, 2). It return 3 for the little island
in the top right. If you set the coordinates to a water coordinate, it
always returns 0.

This really isn’t the best example to illustrate the concept of
recursion. It is simple though. Look up the towers of hanoi, that’s a
much better (aswell as more common) elementary exercise to teach the
concept.

Hope this helped again.

pedro oliva wrote in post #1111496:

Ive been reading Chris P.'s book ‘Learn to Program’ and its been going
great up until I got to chapter 10 on recursion and thus has completely
taken all my excitement from going forward. I understand that recursion
is a method that will continue to call itself till there is an attribute
to cause it to exit the loop. The example in the book though has me all
sorts of confused. Can someone walk me through the example and bring
back the excitement to continue to learn Ruby!

8

Sorry if this reply is a little late.

pedro oliva wrote in post #1111657:

Thanks for the quick replies and all the help.
Tamara and Brandon, Does The Little Schemer apply to Ruby or is it all
Scheme??

The little Schemer only applies to scheme.

example:
#we started with
continent_size(world,5,5) #size=1 here, and now mark this tile as
‘counted tile’

and continue on to
size = size + continent_size(world, x-1, y-1) # 1(size) + (recursion
call with new parameters to continent_size(world, 4 (5-1), 4 (5-1)

Now at this point do we run the line of code we just ran with the new
(world 4,4) parameters and continue to recursively run this till we get
to the base case? In essence keep continuing counting the tiles that are
in a down-left direction till we run out of land to count? Or Do we move
on to the next line of code which would be:

We continue on in the downward direction till we either run out of land
or we find the bounds of the map. That is, the base cases of this
recursive method. So, it will continue to build up a stack of calls
until it gets a return.

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

and pass the (world, 4,4) parameters that we got from the first line of
code, then continuously pass the same parameters all the way down the
rest of the code in the following lines?

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)

You can test this yourself:

def continent_size world, x ,y

print “x: " + x + " y:” y

if x < 0 or x > 10 or y < 0 or y > 10
puts " return bounds of map."
return 0
end

if world[y][x] != ‘land’
puts " return no land found."
return 0
end

…

And you can see the stack build up as it finds more and more land, until
it returns.

9

Thanks for your help Alphonse! Youve been a great help. Sorry for all
the questions would just like to understand this fully before I take on
more info. Im understanding this more and more. Just would like to know
if im understanding this correctly.

So we start with tile (5,5) in the first parameter and find ‘land’ so
now we continue with this method (x-1,y-1) and the next one has ‘no
land’ and now return 0 and count only 1 land.

Now move onto the next method (x,y-1) again starting with parameters
(5,5) and count tile below (5,4) and this has land so now we go back the
first method in the list (x-1,y-1) since there was ‘land’, now giving
parameters (4,3) and this has ‘no land’ and we return 0 counting the 1
land tile.

Since no land was found on (4,3) on the first method (x-1,y-1), now move
to 2nd method (x, y-1) and now we use parameters (5,4) for the method to
give us (5,3)?? Do we use parameters (5,4) because this was the last
tile that had land? Is this the pattern that will continue throughout
the rest of the program?

10

Thanks Alphonse!! That is exactly the help I needed and definitely
helped clear up some things on this program. At first I was not sure as
to how the tiles were being marked a counted. Now my issue im not to
sure how the program proceeds to count beyond the adjacent tiles. For
example:
#we started with
continent_size(world,5,5) #size=1 here, and now mark this tile as
‘counted tile’

and continue on to
size = size + continent_size(world, x-1, y-1) # 1(size) + (recursion
call with new parameters to continent_size(world, 4 (5-1), 4 (5-1)

Now at this point do we run the line of code we just ran with the new
(world 4,4) parameters and continue to recursively run this till we get
to the base case? In essence keep continuing counting the tiles that are
in a down-left direction till we run out of land to count? Or Do we move
on to the next line of code which would be:

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

and pass the (world, 4,4) parameters that we got from the first line of
code, then continuously pass the same parameters all the way down the
rest of the code in the following lines?

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)

Thanks for the quick replies and all the help.
Tamara and Brandon, Does The Little Schemer apply to Ruby or is it all
Scheme??

11

Sounds about right, here’s the first few runs of the block, and when it
returns a basecase:

(5,5) (4,4) return water found
(5,4) (4,3) return water found
(5,3) (4,2) return water found
(5,2) (4,1) (3,0) return water found
(4,0) return water found
(5,0) (4,-1) return map boundaries
(5,-1) return map boundaries
(6,-1) return map boundaries
(4,0) return water found
(6,0) return water found