SICP recursive process vs iterative process: using a recursive procedure to generate an iterative process

by

A recursive process needs to maintain the state of the caller while the recursive call is in progress. For instance, if you wrote:

(define (fact-recurse n)
  (if (< n 2)
      1
      (* n (fact-recurse (- n 1)))))

the outer call has to remember n and wait for the inner call to return before it can perform the multiplication. If you call (fact-recurse 10) there will be 9 stacked multiplications pending when the function reaches the end of its recursion.

But in an iterative process, the earlier state can be discarded. This is possible in the example code because all the information needed is passed as parameters in the recursive call. The variables in the outer call are no longer needed, so nothing needs to be kept on a stack.

Since the outer call’s parameters are no longer needed, the recursive call can be translated into assignments:

(set! product (* counter product))
(set! counter (+ counter 1)
(set! max-count max-count)

and then it just jumps to the beginning of the procedure.

More Related Contents:

  1. Way to go from recursion to iteration
  2. Can every recursion be converted into iteration?
  3. Solution for “Fatal error: Maximum function nesting level of ‘100’ reached, aborting!” in PHP
  4. Determining complexity for recursive functions (Big O notation)
  5. Tower of Hanoi: Recursive Algorithm
  6. Prolog Accumulators. Are they really a “different” concept?
  7. What is recursion and when should I use it?
  8. recursive iteration through nested json for specific key in python
  9. Is Cmake set variable recursive?
  10. recursion versus iteration
  11. Recursive function causing a stack overflow
  12. “application: not a procedure” in binary arithmetic procedures
  13. count the number of calls of a clause
  14. Can all iterative algorithms be expressed recursively?
  15. recursive variadic template to print out the contents of a parameter pack
  16. Multidimensional array iteration
  17. Is a Recursive-Iterative Method Better than a Purely Iterative Method to find out if a number is prime?
  18. SICP example: Counting change, cannot understand
  19. Recursion vs loops
  20. jQuery recursive iteration over objects
  21. Quicksort: Iterative or Recursive
  22. Why should recursion be preferred over iteration?
  23. Implications of foldr vs. foldl (or foldl’)
  24. How does the fibonacci recursive function “work”?
  25. Examples of Recursive functions [closed]
  26. Is it possible to make a recursive closure in Rust?
  27. Recursion or iteration?
  28. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  29. What does “Overflow evaluating the requirement” mean and how can I fix it?
  30. Which recursive functions cannot be rewritten using loops? [duplicate]

Leave a Comment