-- 阶乘
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

-- 斐波那契
fibonacci :: Integer -> Integer
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n-1) + fibonacci (n-2)

-- 列表长度
myLength :: [a] -> Int
myLength []     = 0
myLength (_:xs) = 1 + myLength xs

-- 列表反转
myReverse :: [a] -> [a]
myReverse []     = []
myReverse (x:xs) = myReverse xs ++ [x]

-- 快速排序
qsort :: Ord a => [a] -> [a]
qsort []     = []
qsort (p:xs) = qsort [x | x <- xs, x < p]
               ++ [p]
               ++ qsort [x | x <- xs, x >= p]

// 阶乘
const factorial = (n) => n === 0 ? 1 : n * factorial(n - 1);

// 斐波那契
const fibonacci = (n) => n <= 1 ? n : fibonacci(n - 1) + fibonacci(n - 2);

// 列表长度
const length = (arr) => arr.length === 0 ? 0 : 1 + length(arr.slice(1));

// 快速排序
const qsort = (arr) => {
  if (arr.length <= 1) return arr;
  const [pivot, ...rest] = arr;
  return [
    ...qsort(rest.filter(x => x < pivot)),
    pivot,
    ...qsort(rest.filter(x => x >= pivot)),
  ];
};

# 阶乘
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

# 斐波那契
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# 快速排序
def qsort(arr):
    if len(arr) <= 1:
        return arr
    pivot, *rest = arr
    return qsort([x for x in rest if x < pivot]) + [pivot] + qsort([x for x in rest if x >= pivot])

// 阶乘
fn factorial(n: u64) -> u64 {
    match n {
        0 => 1,
        _ => n * factorial(n - 1),
    }
}

// 快速排序
fn qsort(arr: &[i32]) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr.to_vec();
    }
    let pivot = arr[0];
    let rest = &arr[1..];
    let mut result = qsort(&rest.iter().copied().filter(|&x| x < pivot).collect::<Vec<_>>());
    result.push(pivot);
    result.extend(qsort(&rest.iter().copied().filter(|&x| x >= pivot).collect::<Vec<_>>()));
    result
}

;; 阶乘
(defn factorial [n]
  (if (zero? n) 1
    (* n (factorial (dec n)))))

;; 斐波那契
(defn fibonacci [n]
  (if (<= n 1) n
    (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))

;; 快速排序
(defn qsort [[pivot & rest]]
  (if (nil? pivot) []
    (concat (qsort (filter #(< % pivot) rest))
            [pivot]
            (qsort (filter #(>= % pivot) rest)))))

-- 普通递归（非尾递归）
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)  -- 乘法在递归调用之后

-- 尾递归（使用累加器）
factorial' :: Integer -> Integer
factorial' n = go n 1
  where
    go 0 acc = acc
    go n acc = go (n - 1) (n * acc)  -- 递归调用是最后一步

-- 使用 seq 强制严格求值，确保尾递归优化
factorial'' :: Integer -> Integer
factorial'' n = go n 1
  where
    go 0 acc = acc
    go n acc = acc `seq` go (n - 1) (n * acc)

-- foldl' 本身就是尾递归
factorial''' :: Integer -> Integer
factorial''' n = foldl' (*) 1 [1..n]

// 尾递归版本
const factorial = (n, acc = 1) =>
  n === 0 ? acc : factorial(n - 1, n * acc);

// 蹦床函数（Trampoline）—— 在不支持 TCO 的引擎中实现尾递归
const trampoline = (fn) => {
  let result = fn;
  while (typeof result === 'function') {
    result = result();
  }
  return result;
};

const factorialTrampoline = (n, acc = 1) =>
  n === 0 ? acc : () => factorialTrampoline(n - 1, n * acc);

trampoline(() => factorialTrampoline(100000));  // 不会栈溢出

// 尾递归斐波那契
const fib = (n, a = 0, b = 1) =>
  n === 0 ? a : fib(n - 1, b, a + b);

# 尾递归版本
def factorial(n, acc=1):
    if n == 0:
        return acc
    return factorial(n - 1, n * acc)

# Python 不支持尾递归优化，使用装饰器模拟
import sys

class TailCallException(Exception):
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs

def tail_call_optimized(func):
    def wrapper(*args, **kwargs):
        while True:
            try:
                return func(*args, **kwargs)
            except TailCallException as e:
                args = e.args
                kwargs = e.kwargs
    return wrapper

@tail_call_optimized
def factorial(n, acc=1):
    if n == 0:
        return acc
    raise TailCallException((n - 1, n * acc), {})

# 或者使用循环替代
def factorial_iter(n):
    acc = 1
    for i in range(1, n + 1):
        acc *= i
    return acc

// Rust 编译器会自动进行尾调用优化（在某些情况下）
fn factorial(n: u64, acc: u64) -> u64 {
    match n {
        0 => acc,
        _ => factorial(n - 1, n * acc),
    }
}

// 迭代版本（Rust 风格）
fn factorial_iter(n: u64) -> u64 {
    (1..=n).product()
}

;; Clojure 使用 recur 进行尾递归优化
(defn factorial [n]
  (loop [n n acc 1]
    (if (zero? n) acc
      (recur (dec n) (* n acc)))))

;; 使用 reduce
(defn factorial-reduce [n]
  (reduce * 1 (range 1 (inc n))))

// 通用蹦床
const trampoline = (fn) => (...args) => {
  let result = fn(...args);
  while (typeof result === 'function') {
    result = result();
  }
  return result;
};

// 使用
const even = trampoline((n) => n === 0 ? true : () => odd(n - 1));
const odd = trampoline((n) => n === 0 ? false : () => even(n - 1));

even(1000000);  // true，不会栈溢出

-- CPS 变换
factorialCPS :: Integer -> (Integer -> r) -> r
factorialCPS 0 k = k 1
factorialCPS n k = factorialCPS (n-1) (\res -> k (n * res))

-- 使用
factorialCPS 5 id  -- 120

// JavaScript CPS
const factorialCPS = (n, k = (x) => x) =>
  n === 0 ? k(1) : factorialCPS(n - 1, (res) => k(n * res));

factorialCPS(5);  // 120

# 手动栈管理
def flatten(nested):
    result = []
    stack = [nested]
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            stack.extend(reversed(item))
        else:
            result.append(item)
    return result

mergeSort :: Ord a => [a] -> [a]
mergeSort []  = []
mergeSort [x] = [x]
mergeSort xs  = merge (mergeSort left) (mergeSort right)
  where
    (left, right) = splitAt (length xs `div` 2) xs

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x <= y    = x : merge xs (y:ys)
  | otherwise = y : merge (x:xs) ys

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

binarySearch :: Ord a => [a] -> a -> Maybe Int
binarySearch xs target = go 0 (length xs - 1)
  where
    go lo hi
      | lo > hi   = Nothing
      | midVal == target = Just mid
      | midVal < target  = go (mid + 1) hi
      | otherwise        = go lo (mid - 1)
      where
        mid = (lo + hi) `div` 2
        midVal = xs !! mid

// Y 组合子（非严格版本，使用惰性求值）
const Y = (f) => ((x) => f((y) => x(x)(y)))((x) => f((y) => x(x)(y)));

// 使用 Y 组合子定义阶乘
const factorialGen = (self) => (n) =>
  n === 0 ? 1 : n * self(n - 1);

const factorial = Y(factorialGen);
factorial(5);  // 120

// Z 组合子（严格版本）
const Z = (f) => ((x) => f((...args) => x(x)(...args)))((x) => f((...args) => x(x)(...args)));

-- Haskell 的 Y 组合子
-- 由于惰性求值，可以直接实现
fix :: (a -> a) -> a
fix f = f (fix f)

-- 使用 fix 定义阶乘
factorial :: Integer -> Integer
factorial = fix (\f n -> if n == 0 then 1 else n * f (n - 1))

-- fix 的展开
-- fix f = f (fix f) = f (f (fix f)) = f (f (f ...))

-- 使用 fix 定义斐波那契
fib :: Integer -> Integer
fib = fix (\f n -> if n <= 1 then n else f (n-1) + f (n-2))

# Y 组合子
Y = lambda f: (lambda x: f(lambda y: x(x)(y)))(lambda x: f(lambda y: x(x)(y)))

# 使用
factorial = Y(lambda f: lambda n: 1 if n == 0 else n * f(n - 1))
factorial(5)  # 120

fibonacci = Y(lambda f: lambda n: n if n <= 1 else f(n-1) + f(n-2))
fibonacci(10)  # 55

;; Y 组合子（使用延迟）
(defn Y [f]
  ((fn [x] (f (fn [& args] (apply (x x) args))))
   (fn [x] (f (fn [& args] (apply (x x) args))))))

;; 使用
(def factorial
  (Y (fn [f]
       (fn [n]
         (if (zero? n) 1
           (* n (f (dec n))))))))

(factorial 5)  ;; 120

data Tree a = Leaf | Node (Tree a) a (Tree a)

-- 树的递归操作
treeSize :: Tree a -> Int
treeSize Leaf = 0
treeSize (Node left _ right) = 1 + treeSize left + treeSize right

treeMap :: (a -> b) -> Tree a -> Tree b
treeMap _ Leaf = Leaf
treeMap f (Node left val right) = Node (treeMap left) (f val) (treeMap right)

treeToList :: Tree a -> [a]
treeToList Leaf = []
treeToList (Node left val right) = treeToList left ++ [val] ++ treeToList right

-- 树折叠
foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree _ acc Leaf = acc
foldTree f acc (Node left val right) =
  f (foldTree f acc left) val (foldTree f acc right)

#[derive(Debug)]
enum Tree<T> {
    Leaf,
    Node { left: Box<Tree<T>>, value: T, right: Box<Tree<T>> },
}

impl<T> Tree<T> {
    fn size(&self) -> usize {
        match self {
            Tree::Leaf => 0,
            Tree::Node { left, right, .. } => 1 + left.size() + right.size(),
        }
    }

    fn map<U, F: Fn(&T) -> U>(&self, f: &F) -> Tree<U> {
        match self {
            Tree::Leaf => Tree::Leaf,
            Tree::Node { left, value, right } => Tree::Node {
                left: Box::new(left.map(f)),
                value: f(value),
                right: Box::new(right.map(f)),
            },
        }
    }
}

data List a = Nil | Cons a (List a)

-- 链表操作全部是递归
myLength :: List a -> Int
myLength Nil = 0
myLength (Cons _ xs) = 1 + myLength xs

myAppend :: List a -> List a -> List a
myAppend Nil ys = ys
myAppend (Cons x xs) ys = Cons x (myAppend xs ys)

myReverse :: List a -> List a
myReverse = go Nil
  where
    go acc Nil = acc
    go acc (Cons x xs) = go (Cons x acc) xs

import os
from pathlib import Path

def find_files_recursive(directory, pattern='*.py'):
    """递归查找文件"""
    results = []
    for item in Path(directory).iterdir():
        if item.is_file() and item.match(pattern):
            results.append(item)
        elif item.is_dir():
            results.extend(find_files_recursive(item, pattern))
    return results

# 函数式风格
from functools import reduce

def find_files_fp(directory, predicate):
    def walk(acc, path):
        if path.is_file():
            return acc + [path] if predicate(path) else acc
        elif path.is_dir():
            return reduce(walk, path.iterdir(), acc)
        return acc

    return reduce(walk, Path(directory).iterdir(), [])

// 递归处理嵌套 JSON
const transformValues = (obj, fn) => {
  if (Array.isArray(obj)) {
    return obj.map(item => transformValues(item, fn));
  }
  if (obj !== null && typeof obj === 'object') {
    return Object.fromEntries(
      Object.entries(obj).map(([key, value]) => [key, transformValues(value, fn)])
    );
  }
  return fn(obj);
};

// 使用：将所有字符串值转小写
const data = {
  name: 'ALICE',
  address: { city: 'BEIJING', streets: ['MAIN ST', 'SECOND AVE'] },
};

transformValues(data, v => typeof v === 'string' ? v.toLowerCase() : v);
// { name: 'alice', address: { city: 'beijing', streets: ['main st', 'second ave'] } }