递归中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,直到最外层调用。