RECURSIVE EXPRESSIONS

"Iterating is human, recursivizing is divine" (L. Peter Deutsch).

"The quanta of consciousness is recursion" (Dan Winter).

"I think about thinking" (Douglas Hofstadter).

---

Definition

A recursive expression is an expression that refers to itself.


Remarks

• Recursive expressions may or may not be parameterized.
  
  
• Recursive expressions can be of all types: generic, specific, functions, sequences, sets, etc.
  
  
• Recursive expressions greatly simplify the specification, having been widely used in the definition of derivatives such as, for example, in range, repetition, length, depth, decimal point, etc.
  
  
• Recursive expressions can be evaluated as a finite or infinite expression. In the latter case, one must use potential substitution (the representation).

Examples

1. Recursive sequence:
   
   (x =: (a b c x↓)) // rep. (a b c a b c a b c a b c ...)
x // ev. a
x5 // ev. b
x\6 // ev. c
x7 // ev. a
   
   
2. Factorial of n:
   
   ⟨( fac(n) = (1 ← n=0 →' n*fac(n−1) )⟩
fac(4) // ev. 24
   
   
3. Sum of the first n components of a sequence x:
   
   ⟨( sum(x n) = (0 ← n=0 →' (sum(x n−1) + x + x. )⟩
(x° = ( 1...100 ))
sum(x 100) // ev. 5050
sum(x 50) // ev. 2525
   
   
4. Towers of Hanoi.
   
   

   Towers of Hanoi Starting and ending positions

   
   We have n disks (of sizes 1 to n) inserted, from largest to smallest on a A axis. It is to move the n disks from the A axis to the C axis, using the intermediate B axis as work, so that a disk cannot be placed on top of another disk of smaller size.
   
   The solution strategy is as follows:
   
   
   • Move the n−1 upper disks from A to B, using the working axis C.
   • Move the n disk from A to C.
   • Move the n−1 upper disks from B to C, using the A working axis.
   
   We will represent the motion of a disk i from the x axis to the y axis as (i x y).
   
   Move n disks from the x axis to the z axis using the y working axis.
   
   ⟨( hanoi(n x y z) = ((1 x z) ← n=1 →' ( hanoi(n−1 x z y) (n x z) hanoi(n−1 y x z) ) )⟩

hanoi(1 A B C) // ev.( (1 A C) )
hanoi(2 A B C) // ev. ( (1 A B) (2 A C) (1 B C) )
hanoi(3 A B C) // ev. ( (1 A C) (2 A B) (1 C B) (3 A C) (1 B A) (2 B C) (1 A C) )
   
   
5. Fibonacci sequence:
   
   ⟨( fibo(x y) =: (x y f(x y)) )⟩/⟨( f(u v) = (u+v (f(v u+v))↓ )⟩

fibo(1 1) // rep. (1 1 1 2 3 5 8 13 ...)
fibo(−5 8) // rep. (−5 8 3 11 14 25 ...)
fibo(a b) // rep. (a b a+b a+2*b a+3*b a+4*b ...)

Recursive numbers.

The most important numbers in mathematics have recursive structure, and therefore indicate maximum compression. Examples:

1. The number π:
   
   

   John Wallis formula.

   
   ( π =: 2*f(2)/⟨( f(n) = (n*n).÷(((n−1)*(n+1))*f(n+2) )⟩ )
   
   

   Gregory-Leibniz formula.

   
   ( π =: 4*f(1 +1)/⟨( f(n s) = (1÷n + 1÷f(n+2 −s)) )⟩ )
   
   

   Viète's Formula.

   
   ( π =: 2.÷f(k)/⟨( f(n) = (0 ← n=0 →' f(n−1)*(1÷2 + f(n−1))Ú2 )⟩ )⟩ )
   
   
2. The number e:
   
   

   Euler's Formula.

   
   ( e =: s(1)/⟨( s(n) = 1÷(1*...*n) + s(n+1) )⟩ )
   
   

   Ramanujan's Formula.

   
   ( e =: (1+f(1))/⟨( f(n) = n + (n+1).÷f(n+1)) )⟩ ) )
   
   
3. Neperian logarithm of 2:
   
   
   ( ln(2) = f(1)/⟨( f(n) = 1.÷(n+1) + f(n+2) )⟩ )

Mutual recursion

Occurs when two expressions reference each other. For example:

(x =: (a y↓))
(y =: (b x↓)
x // rep. (a b a b ...)
y // rep. (b a b a b a ...)