Recursion in Ruby
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. Recursion makes the process easier and it reduces a lot of compiling time. In Ruby, we can put all the actions in a loop, so that they can be repeated a number of times. So why is there a need for Recursion?
Since in Ruby, we introduce real-life variables, Recursion plays a vital role in solving major real-life problems in Ruby.
Table of Content
- Iterative Code
- Recursive Code
Iterative Code
We can understand the steps while considering the very simple problem of summing the array. Writing an iterative code would mean running a loop through the array adding each element to a variable and then returning the variable.
Example:
# Iterative program to execute the
# summing of a given array of numbers.
def iterativeSum(arrayofNumbers)
sum = 0
arrayofNumbers.each do |number|
sum += number
end
print sum
end
iterativeSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
Output
55
Recursive Code
In this code, the method calls itself. In the recursive program, the solution to the base case is provided and the solution of the bigger problem is expressed in terms of smaller problems.
Example:
# Recursive method to calculate the sum of all numbers in a given array.
def RecursiveSum(arrayofNumbers)
# Base Case: If the array is empty, return 0.
return 0 if arrayofNumbers.empty?
# Recursive code: Adding each element to the variable by calling the method.
sum = arrayofNumbers.pop
return sum + RecursiveSum(arrayofNumbers)
end
puts RecursiveSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
Output
55
The concept of how the Recursive steps are carried on can be understood using yet another example. In the following example, we would execute a simple program of finding the Factorial of a given number.
The code for the above-mentioned program is as follows:
Example :
# Ruby code for calculating the
# factorial of a number recursively.
def RecursiveFactorial(number)
# Base Case:
if (0..1).include?(number)
return 1
end
#Recursive call:
return number * RecursiveFactorial(number - 1)
end
# Calling the method:
puts RecursiveFactorial(6)
# This code is modified by Susobhan Akhuli
Output
720
Explanation:
The method for calculating the factorial of 6 is called first which further calls the one to calculate for 5 then for 4 until it reaches a point where RecursiveFactorial(1) is called which returns 1 as the answer. Here the recursion calls work as they multiply each call’s result with the already existing answer. The same can be shown in the following steps:
RecursiveFactorial(6) = 6 * RecursiveFactorial(5)
= 6 * 5 * RecursiveFactorial(4)
= 6 * 5 * 4 * RecursiveFactorial(3)
= 6 * 5 * 4 * 3 * RecursiveFactorial(2)
= 6 * 5 * 4 * 3 * 2 * RecursiveFactorial(1)
= 6 * 5 * 4 * 3 * 2 * 1
= 720
Another example is a code for calculating the Nth Fibonacci number. Here the base case would be when the N is less than 2, as then the Fibonacci number would be itself. The recursive call would be calling the method for calculating the (n-1)th and (n-2)nd Fibonacci number and adding it to get the result for the Nth number.
Example:
# Ruby program for calculating the Nth Fibonacci number.
def Fibonacci(number)
# Base case : when N is less than 2.
if number < 2
number
else
# Recursive call : sum of last two Fibonacci's.
return Fibonacci(number - 1) + Fibonacci(number - 2)
end
end
puts Fibonacci(3)
Output:
2
The concept of Recursion solves many problems and makes the process easier as when calculating through the Iterative process. Thus, if a person masters the concept of Recursion, one can solve many problems in less time and with fewer lines of code. However, Recursion in Ruby sometimes produces “SystemStackError: stack level too deep” when a large number is used as an input(This number varies with the system). This means we would have to use an iterative approach to a problem involving large inputs.