Esse post é um foco em cima da parte final do post Vamos memoizar? Desafio da recursão

Um jeito de fazer recursão é fazer uma função que recebe a si mesma.

Para tal, é preciso declarar o tipo da função, para poder passar a ela mesma como referência:

export type RecFunc = (n: number, f: RecFunc) => number;

export function fix_point(f: RecFunc): (x: number) => number {
        return x => f(x, f)
}

E para implementar uma função como essa (por exemplo, função de Fibonacci):

import { RecFunc, fix_point } from './genericMemoization.js'

const fibPrimitive = (n: number, selfFib: RecFunc): number => n <= 0? 0: n == 1? 1: selfFib(n-1, selfFib) + selfFib(n-2, selfFib);

const fib = fix_point(fibPrimitive);
console.log(fib(12)); // 144

É possível extender para quaisquer argumentos de entrada e saída, apenas foquei aqui em entrada e saída com número simples.

Função de Péter-Ackermann:

export type RecFunc2 = (m:number, n: number, f: RecFunc) => number;

export function fix_point2(f: RecFunc2): (x: number, y: number) => number {
        return (x, y) => f(x, y, f)
}

import { RecFunc2, fix_point2 } from './genericMemoization.js'

const ackPrimitive = (m:number, n: number, selfAck: RecFunc2): number => {
  if (m == 0) return n + 1;
  if (n == 0) return selfAck(m-1, 1, selfAck);
  return selfAck(m-1, selfAck(m, n-1, selfAck), selfAck);
}

const ack = fix_point2(ackPrimitive);

Decorando a função

Posso adicionar tratativas simples às recursões. Como, por exemplo, imprimir no console.log toda vida que a função é chamada com os parâmetros passados, no nível correto. Por exemplo, o nível de entrada é 0, depois a cada passagem aumenta em um o nível.

Vamos chamar de param_logger o objeto que vai lidar com isso. Eu posso interagir com ele de 2 maneiras:

logar o que recebi, imprimindo o nível
criar outro param_logger de um nível mais baixo

O param_logger para satisfazer isso precisa ter duas funções:

type ParamLogger = {
    log: (param: number) => void,
    deeper_logger: () => ParamLogger
}

Uma estratégia que não se importa ainda com a correção do deeper_logger seria simplesmente isso:

const lyingLogger: ParamLogger = {
    log: (param: number) => console.log(`0: ${param}`),
    deeper_logger: () => lyingLogger
}

Certo, agora para manter o nível eu preciso de alguma espécie de parâmetro com o nível. Como eu não tenho explícito, isso significa que vou precisar capturar na clausura. Então isso significa que vou precisar de uma função para criar o logger. E ela vai precisar ser recursiva!

const loggerByLevel = (level: number): ParamLogger => ({
    log: (param: number) => console.log(`${level}: ${param}`),
    deeper_logger: () => loggerByLevel(level + 1)
})

Mas eu não devo expor essa função, né? Posso expor apenas o meu baseLogger. Como faço isso? Através de uma IIFE (immediately invoked function expression):

const baseLogger: ParamLogger = (() => {
    const loggerByLevel = (level: number): ParamLogger => ({
        log: (param: number) => console.log(`${level}: ${param}`),
        deeper_logger: () => loggerByLevel(level + 1)
    })
    return loggerByLevel(0)
})();

Agora, para deixar no espírito desse post, vamos passar a função recursivamente para si mesma?

const baseLogger: ParamLogger = (() => {
    type ParamLoggerCreator = (level: number, func: ParamLoggerCreator) => ParamLogger

    const loggerByLevel: ParamLoggerCreator = (level: number, func: ParamLoggerCreator) => ({
        log: (param: number) => console.log(`${level}: ${param}`),
        deeper_logger: () => func(level + 1, func)
    })
    return loggerByLevel(0, loggerByLevel)
})();

Agora, como iríamos lidar com essa decoração? Uma decoração simples no caso do Fibonacci para simplesmente imprimir o parâmetro:

fibPrimitive(12, (n, self) => {
    console.log(n)
    return fibPrimitive(n, self)
})

Note que a função sendo passada recursivamente adiante é a função self, que inicialmente ela é simplesmente uma chamada de console.log com uma chamada da função principal passando self. Agora eu preciso alterar o self.

Vou me basear na implementação feita para memoização, começando, para eventualmente mudar o self:

function fix_point_log(f: RecFunc): (n: number) => number {
    const logging = (n: number, self: RecFunc): number => {
        baseLogger.log(n)
        return f(n, logging)
    }
    return n => logging(n, logging)
}

Hmmm, até aí ok, eu diria. Eu posso simular uma espécie de step também:

function fix_point_log(f: RecFunc): (n: number) => number {
    const logging = (n: number, self: RecFunc): number => {
        baseLogger.log(n)
        const step = (n: number, s: RecFunc): number => {
            return self(n, s)
        }
        return f(n, step)
    }
    return n => logging(n, logging)
}

Ok, step aqui é uma arrow-function. Isso significa que eu posso adicionar propriedades a ela agora:

function fix_point_log(f: RecFunc): (n: number) => number {
    const logging = (n: number, self: RecFunc): number => {
        baseLogger.log(n)
        const step = (n: number, s: RecFunc): number => {
            return self(n, s)
        }
        step.log = baseLogger.deeper_logger()
        return f(n, step)
    }
    return n => logging(n, logging)
}

Qual seria o tipo de step nesse momento?

type TipoDeStep = RecFunc & { log: ParamLogger }

// ou então equivalentemente...

type TipoDeStep = ((n: number, s: RecFunc) => number) & { log: ParamLogger }

// outra maneira...

type TipoDeStep = {
    (n: number, s: RecFunc): number,
    log: ParamLogger
}

Essa terceira notação é a anotação de “call signature” (vide geeksforgeeks). Você até não consegue criar diretamente um objeto callable através de uma arrow-function, mas o TS permite que você coloque o valor logo em seguida. Por exemplo, isso é válido:

type BinOp = {
    (a: number, b: number): number,
    nome: string
}

const soma: BinOp = (a, b) => a + b
soma.nome = "+"

Mas isso é inválido:

type BinOp = {
    (a: number, b: number): number,
    nome: string
}

const soma: BinOp = (a, b) => a + b
// erro de TS
// Property 'nome' is missing in type '(a: number, b: number) => number' but required in type 'BinOp'.ts(2741)

Massa! Agora eu preciso detectar quando o self passado é do tipo com a assinatura de chamada e com o atributo log. O jeito mais fácil é fazendo uma função de guarda!

function isRecFuncEtlog(f: RecFunc): f is RecFunc & { log: ParamLogger } {
    return (f as any)["log"] != null
}

Com isso agora eu posso interceptar e usar o log:

function fix_point_log(f: RecFunc): (n: number) => number {
    const logging = (n: number, self: RecFunc): number => {
        if (isRecFuncEtlog(self)) {
            self.log.log(n)
            return f(n, self)
        }
        baseLogger.log(n)
        const step = (n: number, s: RecFunc): number => {
            return self(n, s)
        }
        step.log = baseLogger.deeper_logger()
        return f(n, step)
    }
    return n => logging(n, logging)
}

Pronto! Agora só falta o passo na chamada de quando é uma função com o log. Vou por a mesma lógica do step, só que agora no lugar de usar o baseLogger.deeper_logger() vou usar o .deeper_logger() do self.log:

function fix_point_log(f: RecFunc): (n: number) => number {
    const logging = (n: number, self: RecFunc): number => {
        if (isRecFuncEtlog(self)) {
            self.log.log(n)
            const step = (n: number, s: RecFunc): number => {
                return self(n, s)
            }
            step.log = self.log.deeper_logger()
            return f(n, step)
        }
        baseLogger.log(n)
        const step = (n: number, s: RecFunc): number => {
            return self(n, s)
        }
        step.log = baseLogger.deeper_logger()
        return f(n, step)
    }
    return n => logging(n, logging)
}