Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. Другими словами, рекурсия - это вызов функции внутри самой себя.

Ниже показан примитивный пример использования рекурсии. По сути, ничего полезного данный код не делает. Более того, такой скрипт (бесконечный) переполнит стэк и аварийно завершит свою работу. Мы получим ошибку: Fatal error: Uncaught Error: Maximum function nesting level of '256' reached, aborting!.

function recursion() 
 {    
  recursion(); 
 }

  recursion();

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

Факториал - произведение всех целых чисел, меньших или равных данному числу. 
function factorial($n) 
{
 if ($n <= 1) return 1; 
 return $n * factorial($n - 1); // здесь происходит повторный вызов функции 
} 

echo factorial(5); // 120

Факториал числа так же можно вычислить, применив цикл, полностью заменяющий рекурсию:

function factorial($n) 
{
 $result = 1; 
 for ($i = 1; $i <= $n; $i++) { 
  $result *= $i; 
 } 
 return $result; 
} 

echo factorial(5); // 120

Практически все данные (за редким исключением) из форм необходимо, во избежания XSS, пропускать через функцию htmlspecialchars(). Наша задача написать такую функцию, которая будет принимать массив (включая вложенные массивы) всех входящих данных и "прогонять" эти данные через встроенную функцию php htmlspecialchars(). И как раз здесь мы будем использовать рекурсию.

<?php
function xss($data) {
 if (is_array($data)) { // Если это массив
  $result = array(); // Создаём новый массив
  foreach ($data as $key => $value) { // Перебираем исходный массив
  	$result[$key] = xss($value); // Рекурсивно вызываем функцию xss
  }
  return $result; // Возвращаемый "защищённый" массив
 }
 return htmlspecialchars($data, ENT_QUOTES); // Если это не массив, то вызываем htmlspecialchars()
}


// Предположим, что в строке запроса у нас такая строка:
// /?name=John&age=<>45
$data = xss($_REQUEST); // Вызываем функцию, передав туда в качестве аргумента весь REQUEST

// Распечатаем результат
var_dump($data);

В данном примере выведем дерево категорий, используя рекурсивный метод, написанный в ООП стиле.

CREATE TABLE IF NOT EXISTS category (
 `id` INT NOT NULL AUTO_INCREMENT,
 `name` VARCHAR(100) NOT NULL,
 `parent_id` VARCHAR(40) NOT NULL,   
 PRIMARY KEY ( id )
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci;

INSERT INTO category (`id`, `name`, `parent_id`) VALUES
(1, 'Компьютеры и периферия', 0),
(2, 'Комплектующие для ПК', 0),
(3, 'Смартфоны и смарт-часы', 0),
(4, 'Телевизоры и медиа', 0),
(5, 'Игры и приставки', 0),
(6, 'Аудиотехника', 0),
(7, 'Фото-видеоаппаратура', 0),
(8, 'Офисная техника и мебель', 0),
(9, 'Компьютерные системы', 1),
(10, 'Периферия', 1),
(11, 'Программное обеспечение и аксессуары', 1),
(12, 'Системные блоки', 9),
(13, 'Моноблоки', 9),
(14, 'Неттопы и компьютеры-флешки', 9),
(15, 'Платформы', 9),
(16, 'Игровые компьютеры', 12),
(17, 'Компьютеры для офиса', 12),
(18, 'Компьютеры для бизнеса', 12),
(19, 'Сенсорные моноблоки', 13),
(20, 'Моноблоки с IPS экраном', 13),
(21, 'Моноблоки с VA экраном', 13),
(22, 'Моноблоки с TN экраном', 13),
(23, 'Основные комплектующие', 2),
(24, 'Хранение данных и охлаждение', 2);

Класс Category:

<?php
require 'DB.php';

class Category
{
  /**
   * @return array
   * Получаем все категории
   */
  public function getData()
  {
    $db = new DB();
    return $db::getRows("SELECT * FROM `category`");
  }

  /**
   * @param $data
   * @return mixed
   * Строим дерево
   */
  public function createTree($data)
  {
    $parents = [];
    foreach ($data as $key => $item):
      $parents[$item->parent_id][$item->id] = $item;
    endforeach;
    $treeElem = $parents[0];
    $this->generateElemTree($treeElem, $parents);
    return $treeElem;
  }

  /**
   * @param $treeElem
   * @param $parents
   * Генерируем элементы дерева с учётом удобного вывода потомков
   */
  private function generateElemTree(&$treeElem, $parents)
  {
    foreach ($treeElem as $key => $item):
      if (!isset($item->children)):
        $treeElem[$key]->children = [];
      endif;

      if (array_key_exists($key, $parents)):
        $treeElem[$key]->children = $parents[$key];
        $this->generateElemTree($treeElem[$key]->children, $parents);
      endif;
    endforeach;
  }

  /**
  * @param $data
  * Рендерим вид
  */
  public function renderTemplate($data) {
  echo "<ul>";
  if(is_array($data)):
   foreach ($data as $item):
    echo '<li>';
    echo "<a href=\"/?=/{$item->id}\">";
    echo $item->name;
    echo "</a>";
    if(count($item->children) > 0):
     $this->renderTemplate($item->children);
    endif;
    echo '</li>';
   endforeach;
  endif;
  echo "</ul>";
 }
}

Выводим дерево категорий:

require 'Category.php';

$category = new Category();
$data = $category->getData();
$tree = $category->createTree($data);
$category->renderTemplate($tree);

Основы хранения в БД древовидных структур можно почитать здесь.