高级数据库设计中，什么是递归关系？递归关系有几种？什么是交叠规则和分离规则？

递归关系就是对自身的引用，多媒体数据库中就是记录与记录之间的直接或间接的调用。递归关系有两种 一对多 多对多 至于分离和交叠规则 就是 ，父类实例与子类实体之间的关系。若父类的实例属于多个字类实体则是交叠规则，若父类实例至多属于一个子类实体则是分离规则。不用谢！^_^

^对于形式如f(n)=g(n)f(n-1)+h(n)的递归方程，可利用递推关系得到：
f(n)=g(n)f(n-1)+h(n)
=g(n)g(n-1)g(n-2)g(1)g(0)[f(0)+
sum[
h(i)/g(i)g(i-1)g(1)]
]。其中，sum表示i从1到n求和。
对上面的式子，可以设n=2^k，则k=logn。则有：
f(k)=2f(k-1)+c2^k
直接应用公式，得：
f(k)=2^k[
csum(2^i/2^i)
]
=2^kck
=cnlogn

动态规划思想和递归思想都是算法设计中常用的思想，它们之间有许多相似之处，但也存在一些不同之处。

动态规划是一种自底向上的算法设计方法，它通常用于求解具有最优子结构性质的问题。动态规划通常需要使用递归来实现，但它们之间的主要区别在于动态规划会将问题的解存储在一个表格中，而不是每次都重新计算，从而提高了算法的效率。

递归则是一种自顶向下的算法设计方法，它通常用于求解具有重复子问题性质的问题。递归算法通常需要使用递归函数来实现，但它们的缺点是在递归过程中可能会重复计算相同的问题，从而导致算法效率低下。

递归函数实现N阶乘

因此，可以说动态规划是一种优化过的递归算法，它通过存储子问题的解来避免了重复计算，从而提高了算法的效率。在某些情况下，动态规划和递归可以相互转化，但在实际应用中，需要根据具体问题选择合适的算法设计方法。

解：(1)用f（i，n）表示涂色方案数，当i=1时，每个方格都可以涂任意一种颜色，即有4N种涂色方案，即f(i,n)=4n，n表示第i个方格时剩余的方格数。
因为需要有偶数个红格，奇数个黄格，设g(i,n,x)表示以第i个方格开始着色为黄格，当前共有n个方格剩余，目前黄格的个数为x时的涂色方案数，则g(i,n,x)=g(i+2,n-2,x+2)+g(i+2,n-2,x)
因为要求有偶数个红格，奇数个黄格，所以x一直要在奇数，当 n=1 时，以红色涂第一个方格，g(1,1,x)只有一种方案f(1,1)=1，当n=2时，需要给2个方格涂色，f(1,2)=3，当n>2时，g(1,n,1)=g(3,n-2,3)+g(3,n-2,1)f(1,n)=g(1,n,1)2
因此有递推关系：f(i,n)=g(i,n,1)2
(2)由于红色不允许相邻，则g(1,n,1)前面的一项即g(3,n-2,1)要忽略，即g(1,n,1)=g(3,n-2,3)，因此有递推关系：f(i,n)=g(i,n,1)

递归，就是在运行的过程中调用自己。构成递归需具备的条件：1 子问题须与原始问题为同样的事，且更为简单；2 不能无限制地调用本身，须有个出口，化简为非递归状况处理。在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。例如，下列为某人祖先的递归定义：某人的双亲是他的祖先（基本情况）。某人祖先的双亲同样是某人的祖先（递归步骤）。斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21 I[1] 斐波纳契数列是典型的递归案例：递归关系就是实体自己和自己建立关系。Fib(0) = 1 [基本情况] Fib(1) = 1 [基本情况] 对所有n > 1的整数：Fib(n) = (Fib(n-1) + Fib(n-2)) [递归定义] 尽管有许多数学函数均可以递归表示，但在实际应用中，递归定义的高开销往往会让人望而却步。例如：阶乘（1) = 1 [基本情况] 对所有n > 1的整数：阶乘（n) = (n 阶乘（n-1)) [递归定义] 一种便于理解的心理模型，是认为递归定义对对象的定义是按照“先前定义的”同类对象来定义的。例如：你怎样才能移动100个箱子？答案：你首先移动一个箱子，并记下它移动到的位置，然后再去解决较小的问题：你怎样才能移动99个箱子？最终，你的问题将变为怎样移动一个箱子，而这时你已经知道该怎么做的。如此的定义在数学中十分常见。例如，集合论对自然数的正式定义是：1是一个自然数，每个自然数都有一个后继，这一个后继也是自然数。

---