Learnerslesson
   JAVA   
  SPRING  
  SPRINGBOOT  
 HIBERNATE 
  HADOOP  
   HIVE   
   ALGORITHMS   
   PYTHON   
   GO   
   KOTLIN   
   C#   
   RUBY   
   C++   




RUBY - RECURSION


Recursion is a technique where a Method calls itself. It might look a little tough. But we will try making it as easy as possible.


Let us understand Recursion using the program to find out the Factorial of a number.


Below is how we calculate the factorial of a number.


Say, we want to calculate the factorial of 3.


3 * 2 * 1 = 6

Similarly, the factorial of 6 is,


6 * 5 * 4 * 3 * 2 * 1 = 720

Below is a program to calculate the factorial of 3 using Recursion.


Example :



def fact(x)
    if x == 1
        return 1
    else
        return (x * fact(x-1))
    end
end        

n = 3
f = fact(n)
puts "The factorial of #{n} is #{f}"


Output :



  The factorial of 3 is 6

In the above code, we are calculating the factorial of 3.


So, we have initialised the value of n with 3.


n = 3

And called the fact(n) Method, passing the value of n(i.e. 3).


f = fact(n)

And the execution of fact Method begins.


def fact(x)
	if x == 1
		return 1
	else
		return (x * fact(x-1))
	end
end

So, the value of x is 3(That is passed as argument).

java_Collections

Then in the next line, we have checked if the value of x is 1. If so, the method execution stops and 1 is returned.


if x == 1
	return 1

Now, since the value of x is 3. We come to the else part and come across the recursive call, where the fact Method calls itself.


else
	return (x * fact(x-1))

But the thing to note is that there is a return statement. A return statement actually means to return the value and finish the Method execution.


But in this case the value will not be returned immediately. Instead, the fact Method calls itself.


And Ruby, maintains an internal Stack that is hidden from the user.


So, in the return statement, if we substitute the value of x with 3.


return (x * fact(x-1))

It becomes return (3 * fact(2)). And that is kept in the internal stack maintained by Ruby.


For fact(3), Ruby keeps a note in stack that the return value is return (3 * fact(2)).And the value of fact(2) is yet to be determined.

java_Collections

Now, fact(2) Method from return (3 * fact(2)) with the new Argument, 2 is called. And the first pass begins.


1st Pass


So, the value of x is 2(That is passed as recursive argument).

java_Collections

And the fact(2)(i.e. After substituting the value of x by 2) Method execution begins with new Argument 2.


def fact(x)
	if x == 1
		return 1
	else
		return (x * fact(x-1))
	end
end

Similarly, the control comes to the else statement and the return statement is encountered.


else:
	return (x * fact(x-1))

Even in this case Ruby finds a recursive call to the fact Method.


So, it stores the value in the stack.


So, in the return statement, if we substitute the value of x with 3.


return (x * fact(x-1))

It is return (2 * fact(1)).

java_Collections

Now, fact(1) Method with the new Argument, 1 is called. And the second pass begins.


2nd Pass


So, the value of x is 1(That is passed as recursive argument).

java_Collections

And the fact(1) Method execution begins with new Argument 1.


def fact(x)
	if x == 1
		return 1
	else
		return (x * fact(x-1))
	end
end

Now, the control comes to the if statement


if x == 1
	return 1

and the return 1 statement is encountered.


Now, Ruby doesn't find a recursive call to the fact Method.


And the return value for fact(1) is 1.

java_Collections

And now, it is time for Ruby to Backtrack


i.e. To get the values out of the Stack.


So Ruby goes to the top element of the stack and takes it out.

java_Collections

And the topmost element is fact(2) with value return (2 * fact(1)). So, it takes out fact(2) and substitutes the value of fact(1) with 1.


And the value of fact(2) becomes,


'fact(2)' -->  'return (2 * fact(1))' -->  return (2*1) --> return 2

So, the value of fact(2) is 2.

java_Collections

So Ruby goes to the stack again.

java_Collections

And the topmost element is fact(3) with value return (3 * fact(2)). So, it takes out fact(3) and substitutes the value of fact(2) with 2.


And the value of fact(3) becomes,


'fact(3)' -->  'return (3 * fact(2))' -->  return (3*2) --> return 6

So, the value of fact(3) is 6.

java_Collections

Now since, the Stack is empty,

java_Collections

Ruby returns the value of fact(3) i.e. 6.


And finally, the value is fact(3) is returned.


f = fact(n)

And the returned value is assigned to f.

java_Collections

And the print statement,


puts "The factorial of #{n} is #{f}"

Prints the output.


The factorial of 3 is 6