Recursion

[Zeriab 9]

I wrote tutorial/explination on recursion to Satiel.

I thought I might as well share it.

It is dedicated to Satiel.

 

 

 

Hey Satiel!

 

Today's topic: Recursion

What is recursion?

I remember this definition roaming around:

Recursion: see "Recursion"

It is clearly meant as joke, but still gives a good idea of what Recursion means.

Recursion means something like going back. Returning... Stuff like that.

Examples are good: Here is a Ruby example of a simple recursive method.

#==============================================================================
# ** Recursion
#------------------------------------------------------------------------------
#  Simple example of recursion
#==============================================================================
class Recursion
 #--------------------------------------------------------------------------
 # * Object Initialization
 #--------------------------------------------------------------------------
 def initialize
 recurse(1)
 end

 #--------------------------------------------------------------------------
 # * Recurse-method
 # 
 # This will print n and then run itself with n being 1
 # greater than before.
 #--------------------------------------------------------------------------
 def recurse(n)
 p n
 recurse(n+1)
 end
end

You see in the method recurse the method recurse being called.

This is called a recursive call because the method is calling itself.

This is classified as Direct Recursion, because the method calls itself.

If the method had called another method which in turn had called recurse it would be classified as Indirect Recursion.

 

You will quickly notice that something is special, especially if you have tried the code. It never stops!

This is because there is nothing in the code preventing the recursive loop to stop.

Well, it will eventually stop because of security measures. (You would get an 'Stack level too deep' error)

If it weren't for them it still would eventually stop due to practical reasons, but it would theoretically never stop.

 

Now we come to the next part. How to prevent it from looping indefinitely:

 

For doing this we must have a base. By a base I mean something that will check if certain conditions are fulfilled. If they are the recursive loop will be breached.

Difficult to understand? Fear not because here is another example:

#==============================================================================
# ** Recursion 2
#------------------------------------------------------------------------------
#  Example of recursion, this time actually usuable.
#==============================================================================
class Recursion
 #--------------------------------------------------------------------------
 # * Object Initialization
 #--------------------------------------------------------------------------
 def initialize
 p recurse(100)
 end

 #--------------------------------------------------------------------------
 # * Recurse-method
 # 
 # Will count the sum of the numbers 1..n recursively
 #--------------------------------------------------------------------------
 def recurse(n)
 # This is the base part
 if n <= 0
 return 0
 else
 # This is the recursive part
 return recurse(n-1) + n
 end
 end
end

If you run Recursion.new you should get the number '5050'.

What is this number? 5050 = 1 + 2 + 3 + ... + 99 + 100

How does method work?

I will show you step by step the execution. I will however use 10 instead of 100 as start number: (55 = 1 + ? + 10)

It will start with 'p recurse(10)' from the object initialization.

This means that the first time the method recurse is called with n = 10

 

recurse(10):

As 10 is not less or equal 0 this command will be executed 'return recurse(10-1) + 10'

The problem is just. What is 'recurse(9)'?

 

recurse(9):

As 9 is not less or equal 0 this command will be executed 'return recurse(9-1) + 9'

You see where this is head? Yes 'recurse(8)'

 

recurse(8):

 

?

 

recurse(1):

Same as before except that the command executed will be 'return recurse(1-1) + 1'

 

recurse(0):

This is different. This time you fulfill the requirements as 0 is less or equal 0.

This makes the method 'return 0'.

So is this it? Is it finished?

recurse(0) is finished.

 

So we go back to recurse(1) which returning 'recurse(0) + 1'

As recurse(0) = 0 we have recurse(1) returning '0 + 1' = '1'

recurse(2) therefore returns '1 + 2' = '3', which then again is used in recurse(3) and so on.

This continues, so recurse(9) returns '36 + 9' = '45'

And finally will recurse(10) return '45 + 10' = '55'

But? won't it just continue?

The answer is no. Remember that we ran the command 'p recurse(10)'?

So when recurse(10) returns its value that is basically it. The value will be printed on the screen like when you normally use the 'p' and we're finished.

 

I think this explains pretty well the idea behind recursion. The idea about solving a problem backwards.

 

This problem can be solved in an iterative way.

Here is a Ruby example of an iterative solution:

#==============================================================================
# ** Recursion 3
#------------------------------------------------------------------------------
#  Same example some before. This time it is iterative.
#==============================================================================
class Recursion
 #--------------------------------------------------------------------------
 # * Object Initialization
 #--------------------------------------------------------------------------
 def initialize
 p recurse(100)
 end

 #--------------------------------------------------------------------------
 # * Recurse-method
 # 
 # Will count the sum of the numbers 1..n iteratively
 #--------------------------------------------------------------------------
 def recurse(n)
 result = 0
 for i in 1..n
 result += i
 end
 return result
 end
end

You see that the method recurse do under any circumstances call itself.

Instead the for-loop iterates 'n' times. For-loop? That is just the 'for i in 1..n' until end.

Each cycle is an iteration. The first iteration is with i = 1, the next with i = 2 and so on.

Iterations are very common. I am only mentioning iteration as opposed to recursion.

 

It now happens that there is an even better way of calculation the sum of 1..n

It can be done by this formula: ((n*n) + n) / 2

So all the classes I have here are basically good-for-nothing except for the purpose I have made them. They help you understand!

 

The task:

Reading is good, but alas reading alone is not as giving as task to follow up the read text.

Here is the task for recursion:

You must make a class with a method that gives the nth Fibonacci number.

The method takes n as input.

You can use the same style as I have used in the examples, but it is not necessary.

What is necessary is that it is done recursive. You can also make an iterative solution. (Optional)

 

What is Fibonacci numbers?

The first Fibonacci number is 0

The second is 1

If n > 2 then the nth Fibonacci number is the (n-1)th Fibonacci number + the (n-2)th Fibonacci number.

For example is the 3th Fibonacci number = 0 + 1 = 1

The 4th = 1 + 1 = 2

The 5th = 1 + 2 = 3

The 6th = 2 + ?

And so on.

 

Good luck with the task.

- Zeriab

 

Sources:

Recursion @ Wikipedia - http://en.wikipedia.org/wiki/Recursion

Introduction to Algorithms - http://mitpress.mit.edu/algorithms/

My head - Sorry, no link to my head