LEARNINGS OF THE WEEK (Jan. 5-9)
By: Frea Diane T. Bautista

This week, we have discussed about Recursion.

Recursion in computer science is a way of thinking about and solving problems. It is, in fact, one of the central ideas of computer science. ^[1] Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem. ^[2]

"The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions." ^[3]

Most high-level computer programming languages support recursion by allowing a function to call itself within the program text. Imperative languages define looping constructs like “while” and “for” loops that are used to perform repetitive actions. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory has proven that these recursive only languages are mathematically equivalent to the imperative languages, meaning they can solve the same kinds of problems even without the typical control structures like “while” and “for”.

Examples of recursively defined procedures (generative recursion)

Factorial

A classic example of a recursive procedure is the function used to calculate the factorial of an integer.

Function definition: 0 \\ \end{cases}" src="http://upload.wikimedia.org/math/9/6/7/967ff33812b62076e5de85fe7fb40b83.png">

Pseudocode (recursive):
function factorial is: input: integer n such that n >= 1 output: [n × (n-1) × (n-2) × … × 1] 1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ] end factorial

A recurrence relation is an equation that relates later terms in the sequence to earlier terms^[6].
Recurrence relation for factorial:
b_n = n * b_n-1
b₀ = 1

Computing the recurrence relation for n = 4:
b4 = 4 * b3 = 4 * 3 * b2 = 4 * 3 * 2 * b1 = 4 * 3 * 2 * 1 * b0 = 4 * 3 * 2 * 1 * 1 = 4 * 3 * 2 * 1 = 4 * 3 * 2 = 4 * 6 = 24

Example Implementations:

Scheme (recursive)	C (recursive)
;; Input: Integer n such that n >= 0 (define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))	//INPUT: n is an integer such that n >= 0 int fact(int n) { if (n == 0) return 1; else return n * fact(n - 1); }