An Introduction to Scheme: Recursion

To understand recursion, you must understand recursion. -- Hunter2011

Recursion is basically a function that calls itself until a condition is met. Recursion can be very useful to solve some kind of problems. When using recursion to solve a problem you need to:

1. Find the base cases of the problem you want to solve. A base case can't be recursive.
2. Analyze the problem to find a recursive solution. \end{enumerate}

Factorial

In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. For example,

4! = 4*3*2*1 = 24

We can describe the cases of the factorial in the following manner:

In Scheme we can write it like this:

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

Fibonacci Sequence

A Fibonacci number is a number that is equal to the sum of the preceding two numbers. The Fibonacci sequence is a set of Fibonacci numbers. The first two Fibonacci numbers are 0 and 1. Dividing the last two numbers of a Fibonacci sequence results in an approximation of the Golden Ratio.

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

In Mathematics, it can be described this way.

F_n = F_{n-1} + F_{n-2}

The cases of the Fibonacci sequence are the following:

In Scheme we can write it like this:

(define fibonacci
    (lambda (n)
    (if (= n 0)
        0
        (if (= n 1)
             1
             (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))))

Lucas Numbers

2, 1, 3, 4, 7, 11, 18, 29, ..., n

Like the Fibonacci sequence, Lucas numbers can be calculated by summing the last 2 numbers of the sequence:

L_n = L_{n-1} + L_{n-2}

Lucas numbers can be calculated like this:

In Scheme we can write it like this:

(define lucas
    (lambda (n)
    (if (= n 0)
        2
        (if (= n 1)
             1
             (+ (lucas (- n 1)) (lucas (- n 2)))))))

Tail Recursion}

Tail-recursive Fibonacci

(define (fibonacci n)
  (seq-iter 1 0 n))

(define (seq-iter a b count)
  (if (= count 0)
      b
      (seq-iter (+ a b) a (- count 1))))

Tail-recursive Fibonacci and Lucas

(define (fibonacci n)
  (seq-iter 1 0 n))

(define (lucas n)
  (seq-iter 1 2 n))

(define (seq-iter a b count)
  (if (= count 0)
      b
      (seq-iter (+ a b) a (- count 1))))

Higher-Order Functions

(define mynums '(1 2 3 4 5))

; map
(map (lambda (x) (* x x)) mynums)
; => (1 4 9 16 25)

(map + mynums (reverse mynums))
; => (6 6 6 6 6)

; for-each
(for-each display mynums)
; 1 2 3 4 5

; apply
(apply + mynums)
; => 15

; filter
(filter (lambda (x) (equal? x 1)) mynums)
; (1)