递归写法

递归是一种函数调用自身的方法，通常用于解决问题的分治思想。在编写递归函数时，需要注意设置递归终止条件，否则会导致无限递归，程序崩溃。

以下是一个递归计算阶乘的示例代码：

def factorial(n):
    if n == 0:  # 终止条件
        return 1
    else:
        return n * factorial(n-1)  # 递归调用

在上面的代码中，当 n 等于 0 时，递归终止，返回 1；否则，递归调用 factorial(n-1) 并将结果与 n 相乘。这样就可以计算 n 的阶乘了。

需要注意的是，递归调用会占用较多的内存和时间，因此在实际应用中，需要根据实际情况选择适当的算法和数据结构。

相关问题

【数据结构】线索化二叉树中序线索化的递归写法和非递归写法

线索化二叉树是一种特殊的二叉树，它的每个节点都有一个指向前驱节点和后继节点的指针，这些指针称为线索。线索化二叉树可以提高遍历二叉树的效率。

中序线索化二叉树的递归写法如下：

def in_order_threading(root):
    global pre
    pre = None
    def in_order_threading_recursive(node):
        global pre
        if not node:
            return
        in_order_threading_recursive(node.left)
        if not node.left:
            node.left = pre
            node.ltag = 1
        if pre and not pre.right:
            pre.right = node
            pre.rtag = 1
        pre = node
        in_order_threading_recursive(node.right)
    in_order_threading_recursive(root)

其中，`node.ltag` 和 `node.rtag` 分别表示节点的左指针和右指针是否是线索，如果是线索，则为1，否则为0。

中序线索化二叉树的非递归写法可以使用栈来实现。具体步骤如下：

1. 从根节点开始，找到最左边的叶子节点，并将路径上所有节点入栈。
2. 当栈不为空时，弹出栈顶节点，并将其线索化。
3. 如果当前节点有右儿子，则将右儿子及其左子树中所有节点入栈，否则继续弹出栈顶节点。

代码实现如下：

def in_order_threading(root):
    pre = None
    stack = []
    node = root
    while node or stack:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if not node.left:
            node.left = pre
            node.ltag = 1
        if pre and not pre.right:
            pre.right = node
            pre.rtag = 1
        pre = node
        node = node.right if not node.rtag else None

需要注意的是，在非递归写法中，需要判断当前节点的右指针是否是线索，如果是线索，则直接将下一个节点设置为该线索指向的节点。

python 递归写法

在Python中，递归是一种函数调用自身的技术，通常用于解决可以被分解为相似或相同子问题的问题。递归函数包含两个主要部分：基本情况（base case）和递归情况（recursive case）。基本情况是函数不再调用自身的终止条件，而递归情况则是将问题规模缩小，直到达到基本情况。

递归的基本步骤如下：
1. **定义基本情况**：确定一个函数不需要再次调用自身就能解决问题的条件。
2. **定义递归情况**：将原问题分解为一个或多个规模较小的子问题，并调用自身解决这些子问题。
3. **返回结果**：每次函数调用结束后，将子问题的解组合起来，形成最终答案。

下面是一个简单的阶乘计算的例子，使用了递归：

def factorial(n):
    # 基本情况：0和1的阶乘是1
    if n == 0 or n == 1:
        return 1
    # 递归情况：n的阶乘是n乘以(n-1)的阶乘
    else:
        return n * factorial(n-1)

# 示例
print(factorial(5))  # 输出：120