广告设计专业英语_黄页企业查询app_世界新闻_网站推广方案策划书2000

递归函数是一种在函数体内直接或间接调用自身的函数。这种函数通过将复杂问题分解为更小的相同问题来解决特定类型的编程任务。

目录

一、递归函数基本概念

1. 递归定义

2. 递归工作原理

 二、递归函数示例

1. 经典阶乘函数

2. 斐波那契数列

3. 计算数字位数

三、递归查询应用

1. 递归WITH子句（公用表表达式）

2. 层次结构查询（员工-经理关系）

 四、递归函数设计要点

 五、递归与迭代对比

1. 递归与迭代对比

2. 迭代实现阶乘（对比） 

六、递归函数的高级应用

1. 遍历树形结构

2. 解决汉诺塔问题

七、递归的局限性及优化

1. Oracle递归深度限制

2. 尾递归优化

3. 记忆化(Memoization)优化

---

一、递归函数基本概念

1. 递归定义

递归函数包含两个关键部分：

• 基准条件（Base Case）：确定递归何时结束，避免无限循环

• 递归条件（Recursive Case）：将问题分解为更小的子问题并调用自身

2. 递归工作原理

• （1）函数检查是否满足基准条件
• （2）如果满足，返回基准值
• （3）如果不满足，将问题分解并调用自身处理更小的子问题
• （4）最终将所有子问题的结果组合成最终解

 二、递归函数示例

1. 经典阶乘函数

CREATE OR REPLACE FUNCTION factorial(p_num IN NUMBER
) RETURN NUMBER
IS
BEGIN-- 基准条件：0!和1!都等于1IF p_num <= 1 THENRETURN 1;ELSE-- 递归条件：n! = n * (n-1)!RETURN p_num * factorial(p_num - 1);END IF;
END factorial;
/-- 调用示例
SELECT factorial(5) FROM dual;  -- 返回120 (5! = 5×4×3×2×1 = 120)

2. 斐波那契数列

CREATE OR REPLACE FUNCTION fibonacci(p_num IN NUMBER
) RETURN NUMBER
IS
BEGIN-- 基准条件IF p_num = 0 THENRETURN 0;ELSIF p_num = 1 THENRETURN 1;ELSE-- 递归条件：F(n) = F(n-1) + F(n-2)RETURN fibonacci(p_num - 1) + fibonacci(p_num - 2);END IF;
END fibonacci;
/-- 调用示例
SELECT fibonacci(10) FROM dual;  -- 返回55 (斐波那契数列第10项)

3. 计算数字位数

CREATE OR REPLACE FUNCTION count_digits(p_num IN NUMBER
) RETURN NUMBER
IS
BEGIN-- 基准条件：单个数字IF p_num BETWEEN -9 AND 9 THENRETURN 1;ELSE-- 递归条件：去掉最后一位后计数+1RETURN 1 + count_digits(TRUNC(p_num/10));END IF;
END count_digits;
/-- 调用示例
SELECT count_digits(12345) FROM dual;  -- 返回5

三、递归查询应用

 Oracle中的递归不仅限于PL/SQL函数，还可以用于SQL递归查询：

1. 递归WITH子句（公用表表达式）

-- 计算1到10的和
WITH recursive_sum(n, total) AS (-- 基准查询SELECT 1, 1 FROM dualUNION ALL-- 递归查询SELECT n+1, total+(n+1)FROM recursive_sumWHERE n < 10
)
SELECT * FROM recursive_sum;/*
结果：
N  TOTAL
1     1
2     3
3     6
4    10
5    15
6    21
7    28
8    36
9    45
10   55
*/

2. 层次结构查询（员工-经理关系）

-- 查找员工的管理链
WITH emp_hierarchy AS (-- 基准查询：从指定员工开始SELECT employee_id, last_name, manager_id, 1 AS levelFROM employeesWHERE employee_id = 110UNION ALL-- 递归查询：向上查找经理SELECT e.employee_id, e.last_name, e.manager_id, h.level + 1FROM employees eJOIN emp_hierarchy h ON e.employee_id = h.manager_id
)
SELECT LPAD(' ', 2*(level-1)) || last_name AS management_chain
FROM emp_hierarchy
ORDER BY level DESC;/*
结果：
MANAGEMENT_CHAINKingHigginsGietz
*/

 四、递归函数设计要点

1. 必须存在基准条件：确保递归能够终止

2. 每次递归应使问题更接近基准条件：避免无限递归

3. 注意递归深度：Oracle有递归深度限制（默认约1000层）

4. 性能考虑：递归可能比迭代解决方案效率低

5. 内存使用：深层递归会消耗大量栈空间

 五、递归与迭代对比

1. 递归与迭代对比

特性	递归	迭代
代码简洁性	更简洁	通常更冗长
内存使用	使用调用栈，可能栈溢出	通常更高效
性能	函数调用开销大	通常更快
适用场景	问题自然递归时	大多数情况
可读性	数学定义清晰时更易读	流程更直观

2. 迭代实现阶乘（对比） 

CREATE OR REPLACE FUNCTION factorial_iter(p_num IN NUMBER
) RETURN NUMBER
ISv_result NUMBER := 1;
BEGINFOR i IN 1..p_num LOOPv_result := v_result * i;END LOOP;RETURN v_result;
END factorial_iter;
/

六、递归函数的高级应用

1. 遍历树形结构

CREATE OR REPLACE PROCEDURE print_folder_tree(p_folder_id IN NUMBER,p_level IN NUMBER DEFAULT 0
) ISCURSOR folder_cur ISSELECT folder_id, folder_nameFROM foldersWHERE parent_id = p_folder_id;
BEGIN-- 打印当前文件夹（带缩进）DBMS_OUTPUT.PUT_LINE(LPAD(' ', p_level*2) || 'Folder: ' || p_folder_id);-- 递归处理子文件夹FOR f_rec IN folder_cur LOOPprint_folder_tree(f_rec.folder_id, p_level + 1);END LOOP;
END print_folder_tree;
/

2. 解决汉诺塔问题

CREATE OR REPLACE PROCEDURE hanoi(p_disks IN NUMBER,p_from IN VARCHAR2,p_to IN VARCHAR2,p_aux IN VARCHAR2
) IS
BEGINIF p_disks = 1 THENDBMS_OUTPUT.PUT_LINE('移动盘子 1 从 ' || p_from || ' 到 ' || p_to);ELSE-- 将n-1个盘子从起始柱移动到辅助柱hanoi(p_disks - 1, p_from, p_aux, p_to);-- 移动第n个盘子到目标柱DBMS_OUTPUT.PUT_LINE('移动盘子 ' || p_disks || ' 从 ' || p_from || ' 到 ' || p_to);-- 将n-1个盘子从辅助柱移动到目标柱hanoi(p_disks - 1, p_aux, p_to, p_from);END IF;
END hanoi;
/-- 调用示例
EXEC hanoi(3, 'A', 'C', 'B');

七、递归的局限性及优化

1. Oracle递归深度限制

 Oracle默认递归深度限制约为1000层，可通过以下方式调整：

ALTER SESSION SET recursive_with_clause = 10000;  -- 增加递归WITH限制

对于PL/SQL递归函数，

可通过修改_recursive_with_balancing等隐藏参数调整限制（需DBA权限）

2. 尾递归优化

Oracle PL/SQL不自动执行尾递归优化，但可手动重构：

-- 普通递归
CREATE OR REPLACE FUNCTION sum_to_n(p_n IN NUMBER
) RETURN NUMBER
IS
BEGINIF p_n <= 1 THENRETURN 1;ELSERETURN p_n + sum_to_n(p_n - 1);END IF;
END;
/-- 尾递归形式（Oracle不会优化，但其他语言可能优化）
CREATE OR REPLACE FUNCTION sum_to_n_tail(p_n IN NUMBER,p_acc IN NUMBER DEFAULT 0
) RETURN NUMBER
IS
BEGINIF p_n <= 0 THENRETURN p_acc;ELSERETURN sum_to_n_tail(p_n - 1, p_acc + p_n);END IF;
END;
/

3. 记忆化(Memoization)优化

缓存已计算结果，避免重复计算：

CREATE OR REPLACE PACKAGE fib_pkg ASTYPE num_array IS TABLE OF NUMBER INDEX BY PLS_INTEGER;g_fib_cache num_array;FUNCTION fibonacci(p_n NUMBER) RETURN NUMBER;
END fib_pkg;
/CREATE OR REPLACE PACKAGE BODY fib_pkg ASFUNCTION fibonacci(p_n NUMBER) RETURN NUMBERISBEGIN-- 基准条件IF p_n = 0 THENRETURN 0;ELSIF p_n = 1 THENRETURN 1;END IF;-- 检查缓存IF g_fib_cache.EXISTS(p_n) THENRETURN g_fib_cache(p_n);END IF;-- 计算并缓存结果g_fib_cache(p_n) := fibonacci(p_n - 1) + fibonacci(p_n - 2);RETURN g_fib_cache(p_n);END;
END fib_pkg;
/

递归函数是解决分治问题和层次结构处理的强大工具，但需要谨慎设计以避免性能问题和栈溢出错误。在Oracle环境中，对于深度递归问题，有时使用迭代方法或递归WITH子句可能是更好的选择。