Functions as Data Transformations: Recursion, Tail Calls, and Efficient Exponentiation & Fibonacci Implementations

The article treats functions as pure data‑to‑data mappings and shows how to express common mathematical operations (factorial, exponentiation, Fibonacci) with recursive and tail‑recursive forms in TypeScript/JavaScript.

Factorial example (imperative version):

function fact(n: number): number {
    let result = 1;
    for (let i = 0; i <= n; i++) {
        result *= i;
    }
    return result;
}

It then discusses the idea that a function can be seen as a mapping between an input model and an output view, similar to the Model→View concept in React.

Simple recursive exponentiation:

function exp(a: number, n: number): number {
    return a * exp(a, n - 1);
}

This version suffers from O(n) recursive calls and possible stack overflow. A tail‑recursive version introduces an accumulator prev:

function expImpl(a: number, prev: number, i: number, n: number): number {
    if (i >= n) {
        return prev;
    }
    return expImpl(a, a * prev, i + 1, n);
}

The tail‑recursive call can be optimized by modern compilers into an iterative loop:

function exp(a: number, n: number): number {
    let i = n;
    let ret = 1;
    while (i > 0) {
        ret = ret * a;
        i--;
    }
    return ret;
}

Using the exponentiation identity (a^(n/2))² = (a²)^(n/2) for even n, a logarithmic‑time version is derived:

function fastExpImpl(a: number, prev: number, i: number): number {
    if (i <= 0) {
        return prev;
    }
    if (i % 2 === 0) {
        return fastExpImpl(a * a, prev, i / 2);
    }
    return fastExpImpl(a, a * prev, i - 1);
}
function fastExp(a: number, n: number): number {
    return fastExpImpl(a, 1, n);
}

The same transformation mindset is applied to the Fibonacci sequence. A naïve recursive definition:

function fib(n: number): number {
    if (n <= 2) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

is replaced by a tail‑recursive version that carries the two previous values as parameters:

function fibImpl(a: number, b: number, i: number, n: number): number {
    if (i <= 1) {
        return a;
    }
    return fibImpl(a + b, a, i - 1, n);
}
function fib(n: number): number {
    return fibImpl(1, 0, n, n);
}

An equivalent iterative version is also provided:

function fibIter(n: number): number {
    let a = 1;
    let b = 0;
    let i = n;
    while (i > 1) {
        a = a + b;
        b = a;
        i--;
    }
    return a;
}

Finally, the article introduces a generic transformation T(p,q) that updates a pair (a,b) by the rules a←b·q + a·q + a·p and b←b·p + a·q. Applying T(p,q) twice yields another transformation T(p',q') whose parameters can be computed from the original p and q. This mirrors the fast exponentiation technique and leads to an O(log n) Fibonacci algorithm, illustrating how functional thinking simplifies algorithm design.

Author: 金智鑫, Team: 共享前端.