什么是递归

概念：

递归，就是在运行的过程中不断地调用自己。递归有两个过程，简单地说一个是递的过程，一个是归的过程。用代码来理解：

const fun=(参数)=> {

    if(结束条件){

        return;

    }

    fun(参数);

    (其他判断条件或者语句)

}

在上边代码中，当第一次进入函数时，先判断是否符合结束条件，如果符合直接结束函数，不符合执行下一个语句，调用自己重新进入下一层自身函数，这个调用自己进入自身函数的操作过程即为“递”的过程。如果进入下一层后符合结束条件的话，return结果，此时之前进入自身函数执行完成返回最外一层函数，最外一层函数递归调用处得到结果，(即内层函数符合条件返回的值)，这个过程即为“归”的过程。这时最外一层函数才能继续执行下一语句，直至函数运行完成。

递归的思想：

递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

递归的应用：

        阶乘的计算：

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

        斐波那契数列：斐波那契数列是以递归的方法定义的，前两个为 0、1，之后的数列元素等于前面两数之和。

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

        杨辉三角的取值：杨辉三角形又称 Pascal 三角形，它的第 i+1 行是(a+b)i 的展开式的系数。 重要性质：三角形中的每个数字等于它两肩上的数字相加。例如杨辉三角的前 5 行：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

递归求 x 行，y 列的杨辉三角的值：

def getValue(x, y):
    if 0 <= y <= x:
        if y == 0 or x == y:
            return 1
        return getValue(x - 1, y - 1) + getValue(x - 1, y)
    return -1

 

        回文字符串的判断：回文字符串就是正读倒读都一样的字符串。如"12321", "abccba"都是回文字符串。 例如，要判断 12321 是否为回文字符串，可分解为 '232' 和首尾的 1 和 1。同样的，232 分解为 3 和头尾的 2 和 2。代码实现如下：

递归法：

def isPalindromeString(s: str):
    if len(s) <= 1:
        return True
    return s[0] == s[-1] and isPalindromeString(s[1:-1])

循环法：

def isPalindromeString(s: str):
    """
    迭代实现
    """
    start = 0
    end = len(s) - 1
    while start < end:
        if s[start] != s[end]:
            return False
        start += 1
        end -= 1
    return True

        字符串全排列：从字符串数组中每次选取一个元素，作为结果中的第一个元素;然后，对剩余的元素全排列。 简单来说，它的思想即为，确定第 1 位，对 n-1 位进行全排列，确定第二位，对 n-2 位进行全排列。。。显然，这是一种递归的思想。

def permutations(arr: str, position: int, end: int):
    if position == end:
        print(arr)
    else:
        for index in range(position, end):
            arr[index], arr[position] = arr[position], arr[index]
            permutations(arr, position + 1, end)
            arr[index], arr[position] = arr[position], arr[index]

总结：递归提高了代码的可读性，思路和逻辑清晰明了。但是内存开销却消耗大，很容易溢出