Scratch编程-递归详解

      从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山…

这其实就是一种递归的现象， 递归，就是在运行的过程中调用自己。你可以把它看成是一个过程函数，也可以是一种算法策略，它在程序设计语言中被广泛利用；它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。像二叉树、著名的汉诺塔等问题都是递归的经典应用。
     用好递归能够简化代码量，特别是在复杂重复的运算中，用递归更能得心应手，算法思路更加清晰，可以这么说‘所有循环能干的活，用递归都能解决’。
      那么要写好一个递归函数从哪里着手呢？我总结有三个点，找好这三点你就能快速写出符合要求的递归函数来。
     一、找好边界条件，一个没有边界的递归会无线循环下去，没有什么实际意义的。
     二、找到最后一次与倒数第二次的关系
     三、假设倒数第二次已经完成（有结果了），那么调用自己求出最后的结果。

以上的分析已经充分考虑了递归的前进和返回了，如果以递归前进与递归返回的思路考虑问题，相信很多人会更懵。
     下边是我分别用Python与Scratch语言，运用递归函数编写的斐波那契数列（Fibonacci）。

def febonacci(n):
    if n <1 or n == 1:
        return n
    else:
        return febonacci(n-2) + febonacci(n-1)

n = int(input())
res = [febonacci(x) for x in range(n)]
print(res)