什么是单项递归，举个例子形象的表述一下

单项递归是指在一个函数的定义中，函数自身只出现一次的递归形式。常见的例子是阶乘函数的递归实现：

int factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

在这个函数中，函数 `factorial` 在定义中只出现了一次，并且调用了自身，因此是单项递归。其功能是计算一个整数的阶乘。当输入值为 0 时，返回结果 1；否则返回 n 乘以 n-1 的阶乘。

相关问题

什么是尾递归，举个例子详细描述一下

尾递归是指一个递归函数中，递归调用是该函数中的最后一步操作。这种递归形式可以被优化，避免栈溢出，提高程序效率。在一些编程语言（如Scheme）中，编译器会自动对尾递归进行优化，将其转化为循环实现。

举个例子，假设我们要计算斐波那契数列的第 n 个数：

int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return n;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

在这个实现中，递归调用出现在 return 语句中，因此不是尾递归。当 n 较大时，递归深度会很大，容易导致栈溢出。

我们可以将其改为尾递归形式，如下所示：

int fibonacci_tail(int n, int a, int b) {
    if (n == 0) {
        return a;
    } else {
        return fibonacci_tail(n-1, b, a+b);
    }
}

int fibonacci(int n) {
    return fibonacci_tail(n, 0, 1);
}

在这个实现中，定义了一个辅助函数 `fibonacci_tail`，其中参数 a 和 b 分别表示斐波那契数列中的前两个数。递归调用出现在 return 语句中，且是该函数的最后一步操作，因此是尾递归。这样递归深度就不会很大，也不容易导致栈溢出。

什么是单向递归，举个例子描述

单向递归是指递归调用的方向是单向的，即每一层递归都是向同一个方向进行的，不会出现递归调用反向的情况。这种递归形式是大多数递归算法所采用的形式。

举个例子，假设我们要实现一个函数来计算一个正整数的二进制表示中 1 的个数：

int count_bits(int n) {
    if (n == 0) {
        return 0;
    } else {
        return n % 2 + count_bits(n / 2);
    }
}

在这个实现中，每一层递归都是向 n/2 的方向进行的，因此是单向递归。函数的基本情况是 n=0，此时返回结果为 0；否则，返回 n 除以 2 的余数加上 n 除以 2 的结果中 1 的个数。这个实现核心思想是利用位运算，将数字不断右移，每次取最低位的值进行累加，直到所有位都被处理完毕。