在编程语言中,函数直接或间接调用本身,则该函数称为递归函数。递归函数提供了不一样的解题思维方式,使用它来解题往往程序要短小的多,思维也会很清晰。
递归函数的应用场景:
1:问题的定义是递归的(阶乘函数、幂函数和斐波那契数列)
2:问题所涉及的数据结构是递归的
3:问题的解法满足递归的性质(Hanoi(汉诺)塔问题)
书写递归函数要掌握的三要素:
1:递归终止条件
2:终止时的处理办法
3:对函数本身的递归调用
问题:用递归函数实现斐波那契数列(1,2,3,5,8,13...)
解析:数学分析可得:
终止条件及其处理办法为 n = 1时,值为1;n = 2时,值为2
当在以上情况外时,值为前两个值之和
==================================================================================
s(n) = 1 n = 1
s(n) = 2 n = 2
s(n) = s(n-1) + s(n-2) n >2
代码:
function s($n){ if($n == 1){ return 1; }else if($n == 2){ return 2; }else{ return s($n - 1) + s($n - 2); } }