共计 4831 个字符，预计需要花费 13 分钟才能阅读完成。
这篇文件介绍一下 递归 ，递归的实质是将原来的问题转化为更小的同一个问题，解决这些更小问题的过程。上面通过两个递归的例子帮忙学习对递归的了解。
1. 递归数组求和
例如某个数组 $arr = [1,2,3,4,5,6,7,8,9,10]; 须要求和，通过实现递归函数对数组求和来帮忙学习对递归的了解。
1.1 输入文件 output_recursion.php
<?php
require 'ArrayRecursion.php';
/**
* 递归实现数组求和
*/
$arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
echo ArrayRecursion::recursionSum($arr);1.2 ArrayRecursion 类
这是一个实现数组递归求和的代码，其中 recursionSum() 是一个递归函数，相当于把求和过程转化为更小的求和，最终实现想要的后果：
<?php
/**
* 应用递归对数组求和 不便对递归的了解
* 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. 递归删除链表某个元素
例如某个链表 10->9->8->99->7->99->6->5->99->4->3->2->1->null 须要删除其中值等于 99 的元素，能够通过实现递归来失去删除指定元素的成果。
2.1 输入文件 output_recursion.php
<?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
*/2.2 LinkedList & Node 链表类
这是一个链表类，能够应用 addFirst() 办法向链表头部增加元素，可应用 getHead() 获取链表 head 节点对象信息，能够应用 setHead() 扭转 head，另外上面定义了一个链表节点类 Node：
<?php
/**
* 链表的实现
* 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 类
这个类定义了一个 deleteElement(LinkedList $linkedList, $val) 办法能够将传进的链表类中指定元素值的节点删除掉 (理论是节点的 next 从新指向)，recursionDelete($head, $val) 办法是一个递归函数，它能递归删除 head 中指定元素值等于 $val 的节点删除:
<?php
/**
* 递归删除链表指定元素
* Class LinkedListRecursion
*/
class LinkedListRecursion
{public static function deleteElement(LinkedList $linkedList, $val) {$linkedList->setHead(self::recursionDelete($linkedList->getHead(), $val));
return $linkedList;
}
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…
扫码关注爱因诗贤公众号
正文完
