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)
    (cond
      ((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)
    (cond
      ((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.

16 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. https://www.accountingmanagerial.com/ says:

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

  12. https://www.aefreezone.com/ 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.

Leave a Reply