Ruby: Recursive Method

Passing a block to a method recursively in ruby

Passing the block is optional, but here, as you already understood, you need it to make your recursive calls. You just pass the block as an additional parameter:

def bubble_sort_by nums, &comparator
  # ...
  bubble_sort_by nums, &comparator if do_it_again
  # ...
end

What is recursion and how does it work?

A recursive function/method calls itself. For a recursive algorithm to terminate you need a base case (e.g. a condition where the function does not call itself recursively) and you also need to make sure that you get closer to that base case in each recursive call. Let's look at a very simple example:

def countdown(n)
  return if n.zero? # base case
  puts n
  countdown(n-1)    # getting closer to base case 
end               

countdown(5)
5
4
3
2
1

Some problems can be very elegantly expressed with recursion, e.g a lot of mathematical functions are described in a recursive way.

Ruby: recursive method

1. The method reverse_append([],4) is called
2. Since 4 >= 0, the return statement does not get called.
3. The method reverse_append([],3) is called.
4. Since 3 >= 0, the return statement does not get called.
5. The method reverse_append([],2) is called.
6. Since 2 >= 0, the return statement does not get called.
7. The method reverse_append([],1) is called.
8. Since 1 >= 0, the return statement does not get called.
9. The method reverse_append([],0) is called.
10. Since 0 >= 0, the return statement does not get called.
11. The method reverse_append([],-1) is called.
12. Since -1 < 0, the array ([]) is returned.
13. We pop up one level in our call stack, to where n = 0 and arr = [].
14. arr << n and arr is returned, so now arr = [0].
15. We pop up one level in our call stack, to where n = 1 and arr = [0].
16. arr << n and arr is returned, so now arr = [0, 1].
17. We pop up one level in our call stack, to where n = 2 and arr = [0, 1].
18. arr << n and arr is returned, so now arr = [0, 1, 2].
19. We pop up one level in our call stack, to where n = 3 and arr = [0, 1, 2].
20. arr << n and arr is returned, so now arr = [0, 1, 2, 3].
21. We pop up one level in our call stack, to where n = 4 and arr = [0, 1, 2, 3].
22. arr << n and arr is returned, so now arr = [0, 1, 2, 3, 4].
23. Finally, the "top-level" method returns, and we have our final result.

How to write a recursive factorial function in Ruby?

Here's how to write the your code in ruby:

def factorial(n)
  return 1 if n == 1
  n * factorial(n - 1)
end

factorial(5)
#=> 120
factorial(7)
#=> 5040

Edit for Stefan's comment:

To avoid a SystemStackError error with large values of n, use the tail-recursive method. Also Ruby's tailcall optimization must be enabled.

# before edit
factorial(100_000).to_s.size
#=> stack level too deep (SystemStackError)

To avoid SystemStackError

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

RubyVM::InstructionSequence.new(<<-CODE).eval
  def factorial(n, acc = 1)
    return acc if n == 1
    factorial(n - 1, n * acc)
  end
CODE

puts factorial(100_000).to_s.size
#=> 456574

Resource 1
Resource 2

adding array elements using recursion

def parts_sums(ls)
  ls.length == 1 ? ls : ([ls.sum] + parts_sums(ls[1..-1]))
end

puts parts_sums([0, 1, 3, 6, 10]).to_s

Ruby + recursive function + defining global variable

The consensus is to avoid global variables as much as possible.

I would either build the collection recursively like this:

def recursive(url)
  ### ...

  result = [] 

  hash["values"].each do |x|
    result << x["links"]["self"]["href"]
  end

  if hash["next"]
    result += recursive(hash["next"])
  end
  result
end

or hand over the collection to the function:

def recursive(url, result = [])
  ### ...

  hash["values"].each do |x|
    result << x["links"]["self"]["href"]
  end

  if hash["next"]
    recursive(hash["next"], result)
  end
  result
end

Either way you can call the function

repo_list = recursive(url)

And I would write it like this:

def recursive(url)
  # ...

  result = hash["values"].map { |x| x["links"]["self"]["href"] }
  result += recursive(hash["next"]) if hash["next"]
  result
end

---

Related Topics