Stack overflow during evaluation (looping recursion?). OCaml

Question

I'm trying to write a function that accepts an int n and returns a list that runs down from n to 0.

This is what I have

let rec downFrom n =
let m = n+1 in
if m = 0 then                                                                                  
  []                                                                                           
else                                                                                            
  (m-1) :: downFrom (m - 1);;

The function compiles ok but when I test it with any int it gives me the error Stack overflow during evaluation (looping recursion?).

I know it's the local varible that gets in the way but I don't know another way to declare it. Thank you!!!

Kristopher Micinski · Accepted Answer · 2012-09-20 22:11:42Z

3

First, the real thing wrong with your program is that you have an infinite loop. Why, because your inductive base case is 0, but you always stay at n! This is because you recurse on m - 1 which is really n + 1 - 1

I'm surprised as to why this compiles, because it doesn't include the rec keyword, which is necessary on recursive functions. To avoid stack overflows in OCaml, you generally switch to a tail recursive style, such as follows:

let downFrom n =
  let rec h n acc = 
    if n = 0 then List.rev acc else h (n-1) (n::acc)
  in
  h n []

Someone suggested the following edit:

let downFrom n =
    let rec h m acc =
        if m > n then acc else h (m + 1) (m::acc)
    in
    h 0 [];

This saves a call to List.rev, I agree.

edited Sep 20, 2012 at 22:11

answered Sep 19, 2012 at 21:54

Kristopher Micinski

7,6823 gold badges31 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

otchkcom Over a year ago

thank you! although i havent learn tail recursion, i changed the last statement to (m-1) :: downFrom (m - 2) and it worked

Kristopher Micinski Over a year ago

as a hint, I would (for better style) simply eliminate the definition of m, and instead replace it by n+1 everywhere, otherwise it looks awkward.

jrouquie Over a year ago

I have corrected a few typos to have your version of downFrom compile. But still, it returns an increasing list, while the OP asks for a decreasing list.

Jeffrey Scofield · Accepted Answer · 2012-09-19 21:55:21Z

1

The key with recursion is that the recursive call has to be a smaller version of the problem. Your recursive call doesn't create a smaller version of the problem. It just repeats the same problem.

answered Sep 19, 2012 at 21:55

Jeffrey Scofield

67k2 gold badges77 silver badges109 bronze badges

Comments

2 revs · Accepted Answer · 2013-01-05 16:17:25Z

0

You can try with a filtering parameter syntax:

let f = function
   p1 -> expr1
 | p2 -> expr2
 | p3 -> ...;;

let rec n_to_one =function
  0->[]
  |n->n::n_to_one (n-1);;

# n_to_one 3;;
- : int list = [3; 2; 1]

edited Jan 5, 2013 at 16:17

community wiki

2 revs
user1308236

Collectives™ on Stack Overflow

Stack overflow during evaluation (looping recursion?). OCaml

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related