New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Recursions not causing StackOverflow #95

Closed
viebel opened this Issue May 3, 2017 · 4 comments

Comments

Projects
None yet
3 participants
@viebel
Contributor

viebel commented May 3, 2017

I was positively surprised to discover that this code was not causing a stack overflow

(define (factorial-rec n)
  (if (= n 1)
      1
      (* n (factorial-rec (- n 1)))))

(factorial-rec 10000)

How could it be?

@amirouche

This comment has been minimized.

Show comment
Hide comment
@amirouche

amirouche May 3, 2017

Contributor

I think biwascheme implement a tranpoline.

Contributor

amirouche commented May 3, 2017

I think biwascheme implement a tranpoline.

@yhara

This comment has been minimized.

Show comment
Hide comment
@yhara

yhara May 4, 2017

Member

BiwaScheme stack is a JavaScript Array and dynamically extended while recursion goes deeper.

Member

yhara commented May 4, 2017

BiwaScheme stack is a JavaScript Array and dynamically extended while recursion goes deeper.

@viebel

This comment has been minimized.

Show comment
Hide comment
@viebel

viebel May 4, 2017

Contributor

Oh. Nice!

Is it required by Scheme standard to prevent stack overflow in deep recursions?

Contributor

viebel commented May 4, 2017

Oh. Nice!

Is it required by Scheme standard to prevent stack overflow in deep recursions?

@viebel viebel closed this May 4, 2017

@yhara

This comment has been minimized.

Show comment
Hide comment
@yhara

yhara May 4, 2017

Member

Is it required by Scheme standard to prevent stack overflow in deep recursions?

The answer is yes, if the function is "tail-recursive".

The requirement is called TCO(tail-call optimization). A Scheme implementation must not grow stack frame for tail calls.
http://stackoverflow.com/questions/310974/what-is-tail-call-optimization

However your factorial-rec is not tail-recursive, so it is implementation dependent that how big n could be.

Member

yhara commented May 4, 2017

Is it required by Scheme standard to prevent stack overflow in deep recursions?

The answer is yes, if the function is "tail-recursive".

The requirement is called TCO(tail-call optimization). A Scheme implementation must not grow stack frame for tail calls.
http://stackoverflow.com/questions/310974/what-is-tail-call-optimization

However your factorial-rec is not tail-recursive, so it is implementation dependent that how big n could be.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment