Stack overflow due to deep recursion

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!!

functional programming does not mean recursion, anyway in a real functional language like haskell, which have tail call optimization, recursing infinitely is not a problem

you can express the word generator as a 900000-sized list, which is actually what I did in my solution, and you can do it in any language:

then just use some variant of map-reduce to count occurences:

the errors you are getting come from for other source beyond the programming language, is more about the algorithm, recursion is not needed

again, functional does not mean recursion

1 Like

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

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

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

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

1 Like

map-reduce is actually the algorithm that powers google

is its functional nature which allows it to be computed easily in a distributed fashion across cooperating clusters

good luck doing things at that scale with OOP

1 Like

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.