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:
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)))))
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)))))))
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)))))))
(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))))
(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))))
(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)