Stack overflow due to deep recursion

training
1

What happens

Hi, I’ve been working in some challenges and I’ve found that due to the features of some challenges I can’t avoid get stack overflow, if I use a functional programming approach.

What do you understand or find about that problem

I got this problem with two different challenges, the problem appear when I need to generate a big amount of data, for example in this challenge: https://www.codeabbey.com/index/task_view/most-frequent-word is necessary generate 900,000 * 6 randoms values, if I use recursion in my function for the random generator, this is not only quite inefficient, but also I got stack overflow before that I can generate the first 9,000 data.

You make any workaround? What did you do?

I tried to program something like a “nested while” using two recursive function, with the objective to limit the depth that each recursive function could reach, but as it was expected, this is not only even more inefficient but also broke my virtual machine every run time :frowning_face: , after that I decided to move to an OOP approach and I found that I can make the work in less than one second. :upside_down_face:

I need help with

I want to know if in this kind of cases when recursion go so deep, is possible to use OOP approach instead of FP, if this not possible I’d want to know if there are some approach that might help to overcome this problem . Thx!!

3

That depends too on how you are making the recursion and which language you are using.

image
image927×356 56.7 KB

for example on erlang, elixir, haskell, etc that is a functional language you can make a tail recursion with high deep and you reach the result in 1 second.

defmodule TailRecursiveFact do
  def main do
    IO.puts(fact(100000))
  end

  def fact(n) do
    recursive_fact(n, 1)
  end

  def recursive_fact(n, a) do
    if n == 0 do
      a
    else fact(n-1, n*a)
    end
  end
end


TailRecursiveFact.main()

And how @wizardly-knuth says, you can use variants of other functions like map(), reduce() or use a mix of both, recursion and Higher-order functions

1 Like
4

for example I get that result in less than 1 second:

image
image1848×890 225 KB

The number is big enough to occupy all of my terminal and still have more numbers.

1 Like
6

Thanks for your clarifications @wizardly-knuth and @pastel-code.

What happens

First I forgot to say that in this moment I’m working with dart, in the past I didn’t realized how much data I was processing because it wasn’t so clear as in these challenges, due to that I started to thought that my problem was the amount of data but I already realized that is not like that, since I started with FP I use tail recursion optimization but I didn’t know that is a feature of functional language.

You make any workaround? What did you do?

After a search I realized that tail call optimization it’s not implemented in Dart and I proved it with the same example of the factorial function and I got stack overflow, so now I know that this is the reason which I can’t avoid the stack overflow.
In the other hand the approach that @wizardly-knuth mention is perfect for this problem so I’m going to try this approach in the other challenge which it’s more complex that this but also got the same problem.