Как элегантно использовать javascript для рекурсивного рисования дерева структуры

JavaScript

рекурсия и хвостовая рекурсия

Проще говоря, рекурсия — это функция, вызывающая сама себя, что широко используется в языках программирования в качестве алгоритма. Его основная идея состоит в том, чтобы преобразовать большую и сложную проблему в меньшую проблему, аналогичную исходной проблеме, которую необходимо решить. В общем, рекурсия требует граничных условий, рекурсивной прямой фазы и рекурсивной фазы возврата. Когда граничные условия не выполняются, рекурсия продолжается, когда граничные условия выполняются, рекурсия возвращается.

Но как квалифицированный программист мы также должны знать, что рекурсивные алгоритмы относительно менее эффективны, чем обычно используемые алгоритмы, такие как обычные циклы. Следовательно, рекурсии следует избегать, насколько это возможно, за исключением случаев, когда нет лучшего алгоритма или существует конкретная ситуация, когда рекурсия является более подходящей. В процессе рекурсивного вызова система открывает стек для хранения точек возврата и локальных количеств каждого уровня.Слишком много раз рекурсии может легко привести к переполнению стека и т.д.

В настоящее время нам нужно использовать хвостовую рекурсию, то есть все рекурсивные вызовы в функции появляются в конце функции.Для хвостовой рекурсии, поскольку существует только одна запись вызова, ошибка «переполнение стека» никогда не возникнет. .

Например, реализуем факториал, если использовать обычную рекурсию, то реализация будет такой:

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

factorial(5) // 120

Необходимо сохранить не более n стеков вызовов, а сложность — O (n).Если мы используем хвостовую рекурсию:

function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5) // 120

На данный момент необходимо сохранить только один стек вызовов, а сложность — O(1). Через этот случай вы постепенно поняли его суть? Далее я представлю несколько общих случаев рекурсивного применения, а затем реализую реализацию дерева, вырезанного из заголовка этой статьи.

Распространенные варианты использования рекурсии

1. Суммирование массива

Для известного массива arr найдите сумму членов arr.

function sumArray(arr, total) {
    if(arr.length === 1) {
        return total
    }
    return sum(arr, total + arr.pop())
}

let arr = [1,2,3,4];
sumArray(arr, arr[1]) // 10

Этот метод передает параметр массива и начальное значение в функцию, которая является первым элементом массива, и реализует суммирование массива по итерации.

2. Последовательность Фибоначчи

Последовательность Фибоначчи, также известная как последовательность золотого сечения, относится к такой последовательности: 1, 1, 2, 3, 5, 8, 13, 21, 34, ... В математике последовательность Фибоначчи определяется рекурсивно как следует: F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n>=3, n∈N*) в современной физике, квази -структура кристаллов, химия и другие области, последовательность Фибоначчи имеет прямое применение. Далее мы используем js для реализации метода нахождения n-го числа Фибоначчи:

// 斐波那契数列
function factorial1 (n) {
    if(n <= 2){
        return 1
    }
    return factorial1(n-1) + factorial1(n-2)
}

// 尾递归优化后
function factorial2 (n, start = 1, total = 1) {
    if(n <= 2){
        return total
    }
    return factorial2 (n -1, total, total + start)
}

Из оптимизированной хвостовой рекурсии функции можно узнать, что каждый раз при вызове функции будут переданы обновленное начальное значение и окончательный результат, а окончательный результат будет получен путем возврата.

3. Факториал

Факториал был упомянут выше, если вы хотите просмотреть его, пожалуйста, прочитайте его.

4. Провинциальные и муниципальные каскадные многоуровневые связи

Суть метода каскадной многоуровневой связи между провинциями и городами заключается в формировании структурированной структуры данных, и соответствующие реализации есть в element или antd, поэтому я не буду здесь слишком много вводить.

5. Глубокое копирование

Пример глубокого копирования уже банален, а вот только простая идея реализации:

function clone(target) {
   if (typeof target === 'object') {
       let cloneTarget = Array.isArray(target) ? [] : {};
       for (const key in target) {
           cloneTarget[key] = clone(target[key]);
       }
       return cloneTarget;
   } else {
       return target;
   }
};

6. Лестничная задача

Всего n шагов, и вы можете пройти только один или два шага за раз Спросите, сколько всего существует способов пройти этот шаг.

n =1; result = 1  --> 1
n =2; result = 2  --> 11 2
n =3; result = 3  --> 111 12 21
...
如果第一步走1个台阶，由以上规律可以发现剩下的台阶有n-1种走法；
如果第一步走2个台阶，由以上规律可以发现剩下的台阶有n-2种走法；
则一共有fn(n-1) + fn(n-2) 种走法
function steps(n) {
    if(n <= 1) {
        return 1
    }
    return steps(n-1) + steps(n-2)
}

7. Форматирование данных объекта

Этот вопрос представляет собой письменный тестовый вопрос, который я когда-то брал у Али.Проблема в том, что если сервер возвращает вложенный объект, регистр имени ключа объекта является неопределенным.Если имя ключа однородно в нижнем регистре.

let obj = {
    a: '1',
    b: {
        c: '2',
        D: {
            E: '3'
        }
    }
}
转化为如下：
let obj = {
    a: '1',
    b: {
        c: '2',
        d: {
            e: '3'
        }
    }
}

// 代码实现
function keysLower(obj) {
    let reg = new RegExp("([A-Z]+)", "g");
    for (let key in obj) {
        if (obj.hasOwnProperty(key)) {
            let temp = obj[key];
            if (reg.test(key.toString())) {
                // 将修改后的属性名重新赋值给temp，并在对象obj内添加一个转换后的属性
                temp = obj[key.replace(reg, function (result) {
                    return result.toLowerCase()
                })] = obj[key];
                // 将之前大写的键属性删除
                delete obj[key];
            }
            // 如果属性是对象或者数组，重新执行函数
            if (typeof temp === 'object' || Object.prototype.toString.call(temp) === '[object Array]') {
                keysLower(temp);
            }
        }
    }
    return obj;
};

Конкретный процесс и идеи прокомментированы в коде, если вам интересно, вы можете изучить его самостоятельно.

8. Переместить каталог/удалить каталог

Мы используем узел здесь для удаления каталога.Существующий API узла имеет функцию удаления каталога, но если в каталоге есть файлы или подкаталоги, fs.rmdir && fs.rmdirSync не может их удалить, поэтому сначала необходимо удалить файлы в каталоге и, наконец, удалите папку.

function deleteFolder(path) {
    var files = [];
    if(fs.existsSync(path)) { // 如果目录存在
        files = fs.readdirSync(path);
        files.forEach(function(file,index){
            var curPath = path + "/" + file;
            if(fs.statSync(curPath).isDirectory()) { // 如果是目录，则递归
                deleteFolder(curPath);
            } else { // 删除文件
                fs.unlinkSync(curPath);
            }
        });
        fs.rmdirSync(path);
    }
}

9. Нарисуйте фрактальную графику

С рекурсией у нас может быть больше свободы в графике, но имейте в виду, что это не лучший вариант.

Мы можем получить вышеуказанный фрактальный узор с помощью некоторых инструментов и рекурсивных идей.

10. Сгладить массив Flat

Сведение массива на самом деле заключается в расширении вложенного массива в массив следующим образом:

let a = [1,2,3, [1,2,3, [1,2,3]]]
// 变成
let a = [1,2,3,1,2,3,1,2,3]
// 具体实现
function flat(arr = [], result = []) {
    arr.forEach(v => {
        if(Array.isArray(v)) {
            result = result.concat(flat(v, []))
        }else {
            result.push(v)
        }
    })
    return result
}

flat(a)

Конечно, это всего лишь один из способов, которым его реализует автор, и вам предстоит изучить другие способы реализации.

Нарисуйте дерево структуры пользовательского стиля с рекурсией

Благодаря приведенному выше введению я думаю, что у всех есть базовая концепция рекурсии и ее применения.Далее я покажу вам шаг за шагом, чтобы нарисовать дерево структуры с рекурсией. Изображение эффекта:

Этот граф представляет собой граф дерева каталогов, созданный в соответствии со структурой каталогов, которая широко используется во многих сценариях приложений.Давайте посмотрим на процесс его реализации:

const fs = require('fs')
const path = require('path')
// 遍历目录/生成目录树
function treeFolder(path, flag = '|_') {
    var files = [];
    
    if(fs.existsSync(path)) {
        files = fs.readdirSync(path);
        files.forEach(function(file,index){
            var curPath = path + "/" + file;
            if(fs.statSync(curPath).isDirectory()) { // recurse
                // obj[file] = treeFolder(curPath, {});
                console.log(flag, file)
                treeFolder(curPath, '   ' + flag)
            } else {
                // obj['--'] = file
                console.log(flag, file)
            }
        })
        // return obj
    }
}

treeFolder(path.resolve(__dirname, './test'))

Тестовый каталог, созданный test, выглядит следующим образом:

Мы реализовали небольшое приложение, которое генерирует дерево структур всего за 10 строк кода. Вам кажется, что рекурсия — это интересно? В этой функции первый параметр — это абсолютный путь к каталогу, второй — идентификатор, идентификатор определяет стиль генерируемых нами веток, и мы можем настраивать разные стили.

Добро пожаловать на взаимный обмен знаниями, вместе исследуя границы фронта.

больше рекомендаций

Категории