CODEWITHSUNDEEP
schemeracket
DemCodeLines
DemCodeLines

Reputation: 1920

Why isn't a function calling itself in its body considered recursive (vs iterative)?

I am learning Scheme/Racket and am confused with recursion-vs-iteration concept.

The specific question is: Write a function that sums up a list of numbers.

Take the following code, for example:

(define (func list)
  (define (dostuff list res)
    (if (empty? list)
        res
        (dostuff (cdr list) (+ (car list) res))))
  (dostuff list 0))

According to the instructor, this is a iterative solution. But I don't understand why. dostuff is calling itself within its implementation, so doesn't that automatically make it recursive?

Or am I missing some concept here?

Upvotes: 1

Views: 250

Answers (2)

Manoel Vilela
Manoel Vilela

Reputation: 904

I recommend the MIT 6.001 lecture 1B of Structure and Interpretations whose the Prof. Gerald Jay Sussman made a graceful explanation about the differences of iteration vs recursion using Scheme (LISP-1).

The biggest difference behind that types of algorithms is linked with the concept of memory and space. Iterative procedures doesn't need know what happened on the previously statements. However, recursive procedures yes.

Think a little about each these algorithms for add:

;; iterative
(define (+ x y)
    (if (= x 0)
         y
        (+ (1- x) (1+ y))))

;; recursive
(define (+ x y)
    (if (= x 0)
         y
         (1+ (+ (1- x) y))))

All them do the same things, but the way of the procedures are executed are different.

If you expand the execution for the first using (+ 3 4) we have that flow:

(+ 3 4)
(+ 2 5)
(+ 1 6)
(+ 0 7)
7

Time=O(n), space=O(1)

However, for the second, see:

(+ 3 4)
(1+ (+ 2 4))
(1+ (1+ (+ 1 4)))
(1+ (1+ (1+ (+ 0 4))))
(1+ (1+ (1+ 4)))
(1+ (1+ 5))
(1+ 6)
7

time=O(n), space=O(n)

Upvotes: 4

C. K. Young
C. K. Young

Reputation: 223073

It's "iterative" because it's tail-recursive. That is, it recurses only in tail position (i.e., the code returns to the caller immediately after the recursion, with no other work, so it's safe to just replace the current call frame with the recursive call's).

In languages like Scheme, which enforces "proper tail calls", tail recursion is effectively a goto. As Alexis's comment says, in Scheme, loops are written using tail recursion, since Scheme does not have a goto.

Upvotes: 4

Related Questions