递归中Return实例分析
函数递归
- 局部函数变量的特性自成体系,作为调用函数自身
- 递归函数不依靠任何外部资源,自成体系的迭代到基准值
return:返回特定的退出状态码,在函数结束时
#! /bin/bash
# using recursion
# 计算阶乘,formula:x!=x*(x-1)!, 使用递归函数得到(x-1)!
function factorial {
# 递归边界,根据1的阶乘是1
if [ $1 -eq 1 ]; then
echo 1
else
local temp=$[ $1 -1 ]
# 接收函数的输出,并将返回值传递给result
local result=$(factorial $temp)
echo $[ $result * $1 ]
fi
}
read -p "Enter value: " value
# result与自成体系的递归函数不同
result=$(factorial $value)
echo "The factorial of $value is : $result"
理解优化
- 当到达递归边界后,函数return最底层被调用并开始回溯
- 递归函数的return(回溯)顺序和调用顺序刚好相反!
那是因为上一层执行递归之后的代码会调用下一层返回的值
亦或者说:最底层的实现(return1)作为最外层的调用(return4),如此循环往复
例如,计算 factorial 4 的过程如下:
-
factorial 4
调用factorial 3
,返回3 * factorial 3
。 -
factorial 3
调用factorial 2
,返回2 * factorial 2
。 -
factorial 2
调用factorial 1
,返回1 * factorial 1
。 -
factorial 1
返回1
。
逐层返回时: -
factorial 2
返回2 * 1 = 2
。 -
factorial 3
返回3 * 2 = 6
。 -
factorial 4
返回4 * 6 = 24
。 -
当递归停止后,函数内部的result返回的是之后的阶乘,因为每一层递归都会将当前的 result 乘以当前的 $1,直到最外层调用。