aleix's blog

add1, sub1 and + recursive process

13 April 2013 4:56 pm (scheme | guile)

In The Little Schemer you are asked to write the function + using the functions zero?, add1 and sub1, such as the result of (+ 46 12) is 58.

(define add1
  (lambda (n) (+ n 1)))

(define sub1
  (lambda (n) (- n 1)))

The solution given is:

(define o+
  (lambda (n m)
      ((zero? m) n)
      (else (add1 (o+ n (sub1 m)))))))

which is correct but has a little problem.

If you are like me (hopefully not), you might have read twenty times the first chapters of SICP (and haven't gone any further). Remember about recursive and iterative processes and recursive procedures? In our o+ case we have a recursive procedure that generates a recursive process, as the process generates a chain of deferred add1 operations.

With a recursive process we can easily blow our stack:

scheme@(guile-user)> (o+ 10 100000)
While executing meta-command:
ERROR: Throw to key `vm-error' with args `(vm-run "VM: Stack overflow" ())'.

This is because this will generate:

(add1 (add1 (add1 (add1 .... (add1 10)))))

with as many add1 as m.

So, how to improve this? With a recursive procedure that generates an iterative process:

(define o+
  (lambda (n m)
      ((zero? m) n)
      (else (o+ (add1 n) (sub1 m))))))

which will generate:

(o+ 11 99999)
(o+ 12 99998)
(o+ 100010 0)

and doesn't overflow the stack.

scheme@(guile-user)> (o+ 10 100000)
$1 = 100010

Yes, this is a tail-recursive function.

42 responses

  1. Steve Darts says:

    Aaah, I see it now.

  2. custom essay writing service says:

    Good thanks for sharing here

  3. Pranshu Kharkwal says:
  4. Law of tort says:

    Great Article.Thanks for sharing such info

  5. NYCResumeServices says:

    Thanks for the post, it was extremely beneficial for me to see that I am not the one facing difficulties with certain subjects. This has helped me greatly and I want to recommend you the NYC Resume Services to return a favor.

  6. Nishant Sharma says:
  7. Az Screen Recorder Apk says:

    Amazin one I must say.

  8. MathCad Online Assignment Help says:

    My friend recommended this blog and he was totally right keep up the fantastic work!

  9. matlab tutoring says:

    Nice post and it would be great for everyone, Thanks a lot for spreading this information here.

  10. SharpPaul says:

    The best paper script service is documented by the best quality. Refer best search engine to get help of professional writers.

  11. says:

    This is really great work. Thank you for sharing such a good and useful information here in the blog for students.

  12. says:

    I am so happy to read this. This is the kind of manual that needs to be given and not the random misinformation that's at the other blogs.

  13. creehack apk says:

    wow nice bru hksj plox like i is writting to get this comment approved so hksj plox hksj plox lolzzz and wow man wow

  14. uktvnow download says:

    nice article.

  15. Ayush Agarwal says:
  16. Jax Teller Sons of Anarchy Vest says:

    you are doing notable service i am definitely loved watching this blog you have got more Trinity university of Florida films so sharing this weblog due to the fact i'm additionally learning in this school. proper activity and hold it up thank you.

  17. lukenlow says:

    An excellent example, I do not cease to admire the sharpness of your mind, you really talent

  18. Our Services says:

    Great Information,it has lot for stuff which is informative.I will share the post with my friends.

  19. Dissertation Writers UK says:

    It’s advised to begin work on an essay early so that you finish on time without any stress. But even the best of plans can go awry because of sudden unexpected events. Don’t let your hard work go to waste. Get our world class essay writing service UK to finish where you left off!

  20. Adana Halı Yıkama says:

    Great Information,it has lot for stuff which is informative

  21. Adana Koltuk YIkama says:

    Great Information

  22. Law Assignment Help says:

    This is really great work. Thank you for sharing such a useful information here in the blog.

  23. Adjustable Dumbbells Review says:

    Things are very open and intensely clear explanation of issues. was truly information. Your website is very beneficial.

  24. Basketball Hoop Reviews 2018 says:

    by visiting this site I found cool stuff here keep it up.

  25. protez tırnak says:

    a very nice place to share. multiply as information is shared

  26. Help With Matlab Project says:

    I personally like your post; you have shared good insights and experiences. Keep it up.

  27. Best Antivirus 2018 says:

    I personally like your blog. Thanks for sharing your experiences and insights with us. Keep it up.

  28. Routerlogin says:

    good to see such content

  29. natwar navetia says:

    thanx for the information you are providing. this is the best post i have ever read.every thing are very open and intensely clear explanation of issues. was truly information. Your website is very beneficial.

  30. screenrecorder says:

    thanx for posting this.loved your post.

  31. Manvendra says:
  32. Matlab Help Online says:

    Good Way Of Telling, Good Post To Take Facts Regarding My Presentation Subject Matter, Which I Am Going To Deliver In My College

  33. Assignment Help says:

    When you must switch to the World Wide Web to search for some Assignment help. Our high expert's professionals who have extensive experience in writing assignment will not only make you avail with the quality assignment, but you will also get plagiarism free assignment within the given time.

  34. All Assignment help reviews says:

    A superior all assignment Help reviews offered by this website with the advantage of online support with high proficiency level based on its latest research and information by professional reviews writers. Wide ranges of subjects are covered with separate writers for each subject.

  35. Reviews says:

    Assignmentservicerating is best reviews site.We at Top Quality Assignment believe that there is no shortcut to success and to attain success, hard work, dedication, and commitment must be present.Allassignmenthelp reviews best reviews site.

  36. Chirag says:
  37. Writing Help says:

    only professional writers can make this kind of material, cheers

  38. Assignments Help says:

    Assignments Help brings to you a comprehensive solution with an assurance of peerless writing style, implemented in every paper.

  39. case study help says:

    I would like to thank you for the efforts you have made in writing this post.

  40. Thesis Help says:

    symonds research Pvt. Ltd. is a leading assignment writing service provider company that provides students assignment help. It also provides dissertation writing and thesis writing service. The student who feels bored and can’t able to do their assignment or essay writing or they are weak in writing. We provide them help to write their assignment and dissertation or done their essay in a cheap or best possible way and deliver the essay in on and before time. So the weak student gets the great in their writing work. We have an all essay writer which has minimum 10 or more years experience in online Essay writing service USA provider field. The team is expertise in writing service.

  41. UK Online Dissertation Help says:

    Nice to be visiting your image your dissertation or UK Online Dissertation writing on one facet of the teeter totter and the modern-day distraction or venture your face on the opposite. your goal needs to now not be to continually have the thesis facet within the air but as a substitute to control the motion from side to side so that after the life facet takes precedence then the dissertation or thesis does not completely hit the ground.

  42. cheap Australian assignment help says:

    Wonderful article. Thanks for taking the time to discuss building a writing habit is the first tool for your motivation toolbox. first, remember that it takes 21 days of constant motion for a new routine to be ingrained on your structures so you now not war against it.

Leave a Reply