Can someone explain how recursion works in these procedures

Question

This is using MIT Scheme, coming from the infamous SICP. I just can't wrap my head around what is happening. Here's a procedure to compute N!.

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

Here's a procedure to compute Fibonacci

(define (fib n)
   (cond ((= n 0) 0)
         ((= n 1) 1)
   (else (+ (fib (- n 1))
            (fib (- n 2))))))

Have you seen recursion in other languages? It might help to know if your question about recursion in Scheme or about recursion in general. — okonomichiyaki, Oct 17 '12 at 18:28
No, I have not seen recursion in languages. I'm asking for recursion in scheme only. — Art, Oct 17 '12 at 18:30
The Fibonacci recursion is discussed in some detail here: http://stackoverflow.com/questions/12920001/recursion-two-calls-in-one-statement The example is in C but that really doesn't matter. — itsbruce, Oct 17 '12 at 21:30
In factorial function uses (if(= 0 1) and it should be (if(=0 n) . current version always return 1. — yilmazhuseyin, Oct 18 '12 at 06:38

Óscar López · Answer 1 · 2012-10-17T22:48:41.143

In the SICP book there's a clear, step-by-step explanation of how linear recursion works (for the factorial example), and there's also a good explanation complete with a nice tree diagram detailing tree recursion (for the fibonacci example).

If you need an easier-to-understand explanation of how recursion works in general in a Scheme program, I'd recommend you take a look at either The Little Schemer or How to Design Programs, both books will teach you how to grok recursive processes in general.

score 1 · Answer 2 · answered Oct 17 '12 at 20:13

Recursion takes some time to understand, so be patient with yourself.

I'd suggest imagining that you were the computer, and stepping through how you would compute (factorial 4). Allow yourself to "be inside" a function multiple times at the same time by thinking of (factorial 4) and (factorial 3) (etc.) as completely different entities.

Can someone explain how recursion works in these procedures

2 Answers2