# 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)