 |
chinesedragon
的主页网址:http://wonyen.net/home.aspx?id=chinesedragon
|
 |
给我留言 |
| § chinesedragon
的【理论研究】专栏
|
| 作者：chinesedragon 发表时间：
2005/12/3 13:45:06 查看：
5977
评论：
5
|
|
| 标题：
递归的简单解释
|
递归的简单解释
最简单的递归具有这样的形式
fn = a | fn
它的结果就是 a
计算过程如下,是一个数学归纳法.
递归次数) 表达式
1) fn = a
2) fn = fn = a
....
n) fn = fn =...(n - 1 次)= fn = a
所以fn = a
写成C语言就是:
#define a 1
int fn(int n)
{
if( n == 0) return a;
return fn(n - 1)
}
n == 0 是递归终止条件, 当它一定能成立时, a 称为吸收子, fn 是递归过程.
当吸收子不含有递归过程(直接或间接)时称为 有限递归. 程序设计中的递归都必须是
有限递归.
不论递归过程如何定义,其关键都产生吸收子.整个递归的过程,实际上就是生成一个
参数数列A = { fn(n=1), fn(n = 2), .... fn(n=n-1)}.
其结果就是以吸收子和参数数列为自变量的一个函数: F(a, A).
上例中, fn(n) 的参数就是n, 参数数列就是A = { n, n - 1, n - 2, ..., 0}
函数F(x, y) = x.所以结果为0.
再举个例子:
void fn ( int n, int sum)
{
if(n == 0) return;
printf("n = %d, sum = %d", n, sum)
fn(n - 1, sum + n);
printf("n = %d, sum = %d", n, sum)
}
这个递归过程
A = {n, sum}, {n - 1, sum + n}, {n - 2, sum + n + n - 1}, ... { 0, sum + n*n - 1 - 2 ... - (n - 1)}
a = 空
F(x, y) = 空.
结果只是打印出了A数列
不过这个例子说明了一个问题, F(x,y)实际上作用了两次. 第一次以A顺序, 第二次以A的逆序.
第一次发生在生成A数列过程中,第二次发生在销毁A的过程中.
实际上它说明了递归的栈本质.
就是说所有的递归函数都可以改写成非递归的函数(使用栈).
如上题:
struct A
{
int n;
int sum;
};
#define N = 30; //最大栈深
void fn(int n, int sum)
{
A stack[N];
int i = n;
stack[n].n = n;
stack[n].sum = sum;
printf("n = %d, sum = %d", stack[i].n, stack[i].sum);
while(i)
{
stack[i - 1].sum = stack[i].sum + i;
stack[i - 1].n = i;
i--;
printf("n = %d, sum = %d", stack[i].n, stack[i].sum);
}
while(i {
printf("n = %d, sum = %d", stack[i].n, stack[i].sum)
i++;
}
}
可以运行的程序见下:
#include <stdio.h>
void fn ( int n, int sum)
{
if(n == 0) return;
printf("before n = %d, sum = %d\n", n, sum);
fn(n - 1, sum + n);
printf("after n = %d, sum = %d\n", n, sum);
}
struct A
{
int n;
int sum;
};
#define N 30 //最大栈深
void fn2(int n, int sum)
{
A stack[N];
int i = n;
stack[n].n = n;
stack[n].sum = sum;
while(i)
{
stack[i - 1].sum = stack[i].sum + i;
stack[i - 1].n = i - 1;
printf("before n = %d, sum = %d\n", stack[i].n, stack[i].sum);
i--;
}
while(i<n)
{
i++;
printf("after n = %d, sum = %d\n", stack[i].n, stack[i].sum);
}
}
int main()
{
fn(5, 0);
fn2(5, 0);
}
 分享到：
|
|
|
|
|
回复者：sskj2009 回复时间：2010/1/15 16:18:20 [第1评]
|
|
promised to  http://www.bestswissreplicas.com/replica-cartier-watches-swiss.html ;Cartier Replica Watches, post the first white http://www.bestswissreplicas.com/replica-panerai-watches-swiss.html ;Panerai Replica Watches, paper for discussion in http://www.bestswissreplicas.com ;cheap rolex replica watches, the May/June 2003 timeframe, the issues dialogue still http://www.bestwatchesreplica.com ;watches replica, had not yet begun http://www.bestwatchesreplica.com/products/iwc-mechanical-classic-watch-iwc-4-486-watch-replica.html ;cheap IWC Mechanical Classic Watch IWC-4-486 watch replica, when this article went http://www.bestwatchesreplica.com ;watches replica, to print in August. In the meantime, IPC and other affected http://www.cheapuggsaleonline.com/products/ugg-womens-bailey-button.html ;cheap ugg UGG Womens Bailey Button sale, industries will have an http://www.cheapuggsaleonline.com/products/ugg-womens-bailey-button.html ;cheap ugg UGG Womens Bailey Button sale, opportunity to comment on http://www.cheapuggsaleonline.com/products/ugg-womens-bailey-button.html ;cheap ugg UGG Womens Bailey Button sale, EPA's planned ICR submission to OMB. The proposed http://www.ebestwatch.com/categories/concord-replicas.html ;exact replica Concord review, ICR, published July 1, http://www.ebestwatch.com/products/patek-philippe-527.html ;exact Patek Philippe Perpetual Calendar P_PHIL-17-774 imitation, is a follow-up to http://www.ebestwatch.com/products/omega-277.html ;replica Omega, OMB's temporary 7-month approval of EPA's ICR in March http://www.hot-handbags.com/louisvuitton-wallets-purse-handbags/replica-louisvuitton-wallets-purse-monogram-vernis-handbags/replica-louis-vuitton-wallet-lvgg-14-handbags.html ;Louis Vuitton Wallet LVgg--14, 2003. OMB's temporary approval, http://www.hot-handbags.com ;replica handbags, which expires October 31, http://www.hot-handbags.com ;replica handbags, required EPA to develop changes to the http://www.replicatiffanyjewelry.net ;replica tiffany jewelry, TRI reporting forms, in http://www.replicatiffanyjewelry.net/categories/replica-tiffany-money-clips.html ;replica Tiffany Money Clips jewelry, order to reduce the http://www.replicatiffanyjewelry.net/products/new-replica-gucci-jewelry-gjewelry0831095.html ;New Replica Gucci Jewelry gjewelry0831095, burden on facilities reporting under TRI. While EP
|
|
|
|
|
|
回复者：腾讯 回复时间：2011/11/20 18:17:14 [第2评]
|
|
|
|
回复者：王博 回复时间：2012/7/24 22:16:42 [第3评]
|
|
|
|
|