python递归算法经典实例有哪些？

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法。

它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

Python

是完全面向对象的语言。函数、模块、数字、字符串都是对象。并且完全支持继承、重载、派生、多继承，有益于增强源代码的复用性。Python支持重载运算符和动态类型。相对于Lisp这种传统的函数式编程语言，Python对函数式设计只提供了有限的支持。有两个标准库(functools, itertools)提供了Haskell和Standard ML中久经考验的函数式程序设计工具。

递归，简单的说就是自己调用自己，执行递归函数降反复调用其自身，每调用一次就进入新的一层。例如，有函数f如下。

int f(int x)

{

int y

z=f(y)

return z

}

这个函数是一个递归函数，但是运行该函数将无休止的调用自身，这当然是不正确的，在此只是给你举个简单的例子而已。为了防止调用无休止的进行，必须加条件判断，满足某种条件后就不再做递归调用，然后逐层返回。在此举例说明递归调用的执行过程。

用递归法计算n!.

long f(int i)

{

if(n<0) printf("input error")return

else if(i==0||i==1) return 1

else return i*f(i-1)

}

main()

{

int n

printf("please input n:\n")

scanf("%d",&n)

printf("%d=%id\n",n,f(n))

}

程序中的f是一个递归函数，如果n<0,n==0或者n==1时将结束函数的执行，否则就递归调用f函数自身。

假设输入3，即求3！。进入f函数i=3,不等于0或1，所以执行i*f(i-1),即

3*f（2）。然后再递归调用f(2),2不等于0或1，所以执行i*f(i-1),即2*f(1).继续调用f(1),此时1==1，结束函数的执行。

所以返回的结果是3*f(2)=3*2*f(1)=3*2*1=6.

希望你可以看懂，我感觉蛮简单的。

举一个用递归调用函数求输入非负整数的阶乘的例子，如下：

//#include "stdafx.h"//If the vc++6.0, with this line.

#include "stdio.h"

int fact(int n){

    if(n==1 || n==0) return 1

    else return n*fact(n-1)

}

int main(void){

    int x

    while(1){

        printf("Input x(int 12>=x>=0)...\nx=")

        if(scanf("%d",&x),x>=0 && x<=12)//x>12时会使结果溢出

            break

        printf("Error,redo: ")

    }

    printf("%d! = %d\n",x,fact(x))

    return 0

}

---