前言前言前言这篇文章介绍一下 递归，递归的本质是将原来的问题转化为更小的同一个问题，解决这些更小问题的过程。下面通过两个递归的例子帮助学习对递归的理解。1.递归数组求和1.递归数组求和1.递归数组求和例如某个数组 $arr = [1,2,3,4,5,6,7,8,9,10]; 需要求和，通过实现递归函数对数组求和来帮助学习对递归的理解。1.1 输出文件 output_recursion.php
require 'ArrayRecursion.php';
/**
* 递归实现数组求和
*/
$arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
echo ArrayRecursion::recursionSum($arr);
require 'ArrayRecursion.php';
/**
* 递归实现数组求和
*/
$arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
echo ArrayRecursion::recursionSum($arr);1.2 ArrayRecursion 类1.2 ArrayRecursion 类这是一个实现数组递归求和的代码，其中 recursionSum() 是一个递归函数，相当于把求和过程转化为更小的求和，最终实现想要的结果：
/**
* 使用递归对数组求和 方便对递归的理解
* Class ArrayRecursion
*/
class ArrayRecursion
{

public static function sum(array $arr) {

return self::recursionSum($arr);

}

public static function recursionSum(array $arr, $i = 0) {

if (count($arr) == $i) {

return 0;

}

return $arr[$i] + self::recursionSum($arr, $i + 1);

}
}
/**
* 使用递归对数组求和 方便对递归的理解
* Class ArrayRecursion
*/
class ArrayRecursion
{

public static function sum(array $arr) {

return self::recursionSum($arr);

}

public static function recursionSum(array $arr, $i = 0) {

if (count($arr) == $i) {

return 0;

}

return $arr[$i] + self::recursionSum($arr, $i + 1);

}
}Tips：这个求和过程仅仅只是帮助学习递归思想，实际求和可以直接遍历数组。2.递归删除链表某个元素2.递归删除链表某个元素2.递归删除链表某个元素例如某个链表 10->9->8->99->7->99->6->5->99->4->3->2->1->null 需要删除其中值等于 99 的元素，可以通过实现递归来得到删除指定元素的效果。2.1 输出文件 output_recursion.php2.1 输出文件 output_recursion.php
require 'LinkedList.php';
require 'LinkedListRecursion.php';
/**
* 首先实例化一个链表，向链表中添加50个元素
*/
$linkedList = new LinkedList();
for ($i = 0; $i < 50; $i++) {

if ($i % 7 == 0) {

$linkedList->addFirst(99);

} else {

$linkedList->addFirst($i);

}
}
echo $linkedList->toString();
/**打印链表中元素
* 99->48->47->46->45->44->43->99->41->40->39->
* 38->37->36->99->34->33->32->31->30->29->99->27->
* 26->25->24->23->22->99->20->19->18->17->16->15->
* 99->13->12->11->10->9->8->99->6->5->4->3->2->1->99->null
*/
//将链表对象传入一个能删除指定元素的方法，如 99
echo LinkedListRecursion::deleteElement($linkedList, 99)->toString();
/**打印
* 48->47->46->45->44->43->41->40->
* 39->38->37->36->34->33->32->31->
* 30->29->27->26->25->24->23->22->
* 20->19->18->17->16->15->13->12->
* 11->10->9->8->6->5->4->3->2->1->null
*/
require 'LinkedList.php';
require 'LinkedListRecursion.php';
/**
* 首先实例化一个链表，向链表中添加50个元素
*/
$linkedList = new LinkedList();
for ($i = 0; $i < 50; $i++) {

if ($i % 7 == 0) {

$linkedList->addFirst(99);

} else {

$linkedList->addFirst($i);

}
}
echo $linkedList->toString();
/**打印链表中元素
* 99->48->47->46->45->44->43->99->41->40->39->
* 38->37->36->99->34->33->32->31->30->29->99->27->
* 26->25->24->23->22->99->20->19->18->17->16->15->
* 99->13->12->11->10->9->8->99->6->5->4->3->2->1->99->null
*/
//将链表对象传入一个能删除指定元素的方法，如 99
echo LinkedListRecursion::deleteElement($linkedList, 99)->toString();
/**打印
* 48->47->46->45->44->43->41->40->
* 39->38->37->36->34->33->32->31->
* 30->29->27->26->25->24->23->22->
* 20->19->18->17->16->15->13->12->
* 11->10->9->8->6->5->4->3->2->1->null
*/2.2 LinkedList & Node 链表类2.2 LinkedList & Node 链表类这是一个链表类，可以使用 addFirst() 方法向链表头部添加元素，可使用 getHead() 获取链表 head 节点对象信息，可以使用 setHead() 改变 head，另外下面定义了一个链表节点类 Node：
/**
* 链表的实现
* Class LinkedList
*/
class LinkedList
{

private $dummyHead;

private $size;

/**

* 初始化链表 null->null

* LinkedList constructor.

*/

public function __construct() {

$this->dummyHead = new Node(null, null);

$this->size = 0;

}

/**

* 获取链表大小

* @return int

*/

public function getSize(): int {

return $this->size;

}

/**

* 判断链表是否为空

* @return bool

*/

public function isEmpty(): bool {

return $this->size == 0;

}

/**

* 在链表的第 index 位置添加元素

* @param int $index

* @param $e

*/

public function add(int $index, $e): void {

if ($index < 0 || $index > $this->size) {

echo "索引范围错误";

exit;

}

$prve = $this->dummyHead;

for ($i = 0; $i < $index; $i++) {

$prve = $prve->next;

}

//将上插入位置的上一个位置的 next 节点指向插入节点，插入节点的 next 节点信息指向原上节点的 next 节点

$prve->next = new Node($e, $prve->next);

$this->size++;

}

/**

* 向链表开头添加元素

* @param $e

*/

public function addFirst($e): void {

$this->add(0, $e);

}

/**

* 向链表末尾添加元素

* @param $e

*/

public function addLast($e): void {

$this->add($this->size, $e);

}

/**

* 获取链表第 index 位置元素

* @param $index

*/

public function get($index) {

if ($index < 0 || $index > $this->size) {

echo "索引范围错误";

exit;

}

$node = $this->dummyHead;

for ($i = 0; $i < $index + 1; $i++) {

$node = $node->next;

}

return $node->e;

}

/**

* 获取链表第一个元素

* @return mixed

*/

public function getFirst() {

return $this->get(0);

}

/**

* 获取链表最后一个元素

* @return mixed

*/

public function getLast() {

return $this->get($this->size - 1);

}

/**

* 修改链表中第 index 位置元素值

* @param $index

* @param $e

*/

public function update($index, $e) {

if ($index < 0 || $index > $this->size) {

echo "索引范围错误";

exit;

}

$node = $this->dummyHead;

for ($i = 0; $i < $index + 1; $i++) {

$node = $node->next;

}

$node->e = $e;

}

/**

* 判断链表中是否存在某个元素

* @param $e

* @return bool

*/

public function contains($e): bool {

for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {

if ($node->e == $e) {

return true;

}

}

return true;

}

/**

* 删除链表中第 index 位置元素

* @param $index

*/

public function remove($index) {

if ($index < 0 || $index > $this->size) {

echo "索引范围错误";

exit;

}

if ($this->size == 0) {

echo "链表已经是空";

exit;

}

$prve = $this->dummyHead;

for ($i = 0; $i < $index; $i++) {

$prve = $prve->next;

}

$node = $prve->next;

$prve->next = $node->next;

$this->size--;

return $node->e;

}

/**

* 删除链表头元素

*/

public function removeFirst() {

return $this->remove(0);

}

/**

* 删除链表末尾元素

*/

public function removeLast() {

return $this->remove($this->size - 1);

}

/**

* 获取头结点信息

* @return mixed

*/

public function getHead() {

return $this->dummyHead->next;

}

/**

* 设置头

* @param Node $head

*/

public function setHead(Node $head) {

$this->dummyHead->next = $head;

}

/**

* 链表元素转化为字符串显示

* @return string

*/

public function toString(): string {

$str = "";

for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {

$str .= $node->e . "->";

}

return $str . "null";

}
}
class Node
{

public $e;//节点元素

public $next; //下个节点信息

/**

* 构造函数 设置节点信息

* Node constructor.

* @param $e

* @param $next

*/

public function __construct($e, $next) {

$this->e = $e;

$this->next = $next;

}
}
/**
* 链表的实现
* Class LinkedList
*/
class LinkedList
{

private $dummyHead;

private $size;

/**

* 初始化链表 null->null

* LinkedList constructor.

*/

public function __construct() {

$this->dummyHead = new Node(null, null);

$this->size = 0;

}

/**

* 获取链表大小

* @return int

*/

public function getSize(): int {

return $this->size;

}

/**

* 判断链表是否为空

* @return bool

*/

public function isEmpty(): bool {

return $this->size == 0;

}

/**

* 在链表的第 index 位置添加元素

* @param int $index

* @param $e

*/

public function add(int $index, $e): void {

if ($index < 0 || $index > $this->size) {

echo "索引范围错误";

exit;

}

$prve = $this->dummyHead;

for ($i = 0; $i < $index; $i++) {

$prve = $prve->next;

}

//将上插入位置的上一个位置的 next 节点指向插入节点，插入节点的 next 节点信息指向原上节点的 next 节点

$prve->next = new Node($e, $prve->next);

$this->size++;

}

/**

* 向链表开头添加元素

* @param $e

*/

public function addFirst($e): void {

$this->add(0, $e);

}

/**

* 向链表末尾添加元素

* @param $e

*/

public function addLast($e): void {

$this->add($this->size, $e);

}

/**

* 获取链表第 index 位置元素

* @param $index

*/

public function get($index) {

if ($index < 0 || $index > $this->size) {

echo "索引范围错误";

exit;

}

$node = $this->dummyHead;

for ($i = 0; $i < $index + 1; $i++) {

$node = $node->next;

}

return $node->e;

}

/**

* 获取链表第一个元素

* @return mixed

*/

public function getFirst() {

return $this->get(0);

}

/**

* 获取链表最后一个元素

* @return mixed

*/

public function getLast() {

return $this->get($this->size - 1);

}

/**

* 修改链表中第 index 位置元素值

* @param $index

* @param $e

*/

public function update($index, $e) {

if ($index < 0 || $index > $this->size) {

echo "索引范围错误";

exit;

}

$node = $this->dummyHead;

for ($i = 0; $i < $index + 1; $i++) {

$node = $node->next;

}

$node->e = $e;

}

/**

* 判断链表中是否存在某个元素

* @param $e

* @return bool

*/

public function contains($e): bool {

for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {

if ($node->e == $e) {

return true;

}

}

return true;

}

/**

* 删除链表中第 index 位置元素

* @param $index

*/

public function remove($index) {

if ($index < 0 || $index > $this->size) {

echo "索引范围错误";

exit;

}

if ($this->size == 0) {

echo "链表已经是空";

exit;

}

$prve = $this->dummyHead;

for ($i = 0; $i < $index; $i++) {

$prve = $prve->next;

}

$node = $prve->next;

$prve->next = $node->next;

$this->size--;

return $node->e;

}

/**

* 删除链表头元素

*/

public function removeFirst() {

return $this->remove(0);

}

/**

* 删除链表末尾元素

*/

public function removeLast() {

return $this->remove($this->size - 1);

}

/**

* 获取头结点信息

* @return mixed

*/

public function getHead() {

return $this->dummyHead->next;

}

/**

* 设置头

* @param Node $head

*/

public function setHead(Node $head) {

$this->dummyHead->next = $head;

}

/**

* 链表元素转化为字符串显示

* @return string

*/

public function toString(): string {

$str = "";

for ($node = $this->dummyHead->next; $node != null; $node = $node->next) {

$str .= $node->e . "->";

}

return $str . "null";

}
}
class Node
{

public $e;//节点元素

public $next; //下个节点信息

/**

* 构造函数 设置节点信息

* Node constructor.

* @param $e

* @param $next

*/

public function __construct($e, $next) {

$this->e = $e;

$this->next = $next;

}
}2.3 LinkedListRecursion 类2.3 LinkedListRecursion 类这个类定义了一个 deleteElement(LinkedList $linkedList, $val) 方法可以将传进的链表类中指定元素值的节点删除掉(实际是节点的 next 重新指向)，recursionDelete($head, $val) 方法是一个递归函数，它能递归删除 head 中指定元素值等于 $val 的节点删除:
/**
* 递归删除链表指定元素
* Class LinkedListRecursion
*/
class LinkedListRecursion
{

public static function deleteElement(LinkedList $linkedList, $val) {

$linkedList->setHead(self::recursionDelete($linkedList->getHead(), $val));

return $linkedList;

}



/**

* 递归函数 递归删除链表元素

* @param $head

* @param $val

* @return null

*/

private static function recursionDelete($head, $val) {

if ($head == null) {

return null;

} else {

if ($head->e == $val) {

return self::recursionDelete($head->next, $val);

} else {

$head->next = self::recursionDelete($head->next, $val);

return $head;

}

}

}
}
/**
* 递归删除链表指定元素
* Class LinkedListRecursion
*/
class LinkedListRecursion
{

public static function deleteElement(LinkedList $linkedList, $val) {

$linkedList->setHead(self::recursionDelete($linkedList->getHead(), $val));

return $linkedList;

}



/**

* 递归函数 递归删除链表元素

* @param $head

* @param $val

* @return null

*/

private static function recursionDelete($head, $val) {

if ($head == null) {

return null;

} else {

if ($head->e == $val) {

return self::recursionDelete($head->next, $val);

} else {

$head->next = self::recursionDelete($head->next, $val);

return $head;

}

}

}
}代码仓库 ：https://gitee.com/love-for-po...https://gitee.com/love-for-po总结总结总结