C语⾔—递归⼆分法查
分治策略：分解的是规模，⽐如数10亿硬币，分成4万个⼈区完成，这样，问题不会改变，改变的是问题的规模
下⾯是不⽤递归求阶乘的⽅式
int fun(int n)
{
int sum=1;
for(int i=1;i<=n;i++)
{
sum=sum*(sum+1);
}
}
void main{
int n,sum;
cin>>n;
sum=fun(n);
sum=fac(n);
}
这是递归的算法
int fac(n)
{
if(n<=1)return1;
else return fac(n-1)*n;
}
fun(n)的时间复杂度是O（n），空间复杂度为O（1）是⼀个定值，不会随着i的范围变化开辟更⼤的内存空间。fac(n)的时间复杂度是O（n），空间复杂度为O（n）。所以在能⽤循环的时候尽量少使⽤递归。虽然递归的代码简洁。
系统默认给每个程序分配的栈⼤⼩为1M，有死循环之说，但是没有⽆限递归之说，如果递归要使⽤很多次时，要注意超出范围。
上图为⼀个⽆限递归的例⼦
下⾯是⼆分法查的使⽤循环的操作
#define error -1
int binaryfindvalue(Seqlist&seq,const elemtype val)
{
int left =0;
int right = seq.cursize-1;
int mid;
while(1)
{
if(left < right)
{
return error;
}
mid =(left + right)/2;//如果担⼼数据范围超过int的最⼤范围
//这⾥的式⼦改为(right -left+1)/2+left
c语言用递归函数求n的阶乘if(val < seq.data[mid])
{
right = mid -1;
}
else if(val > seq.data[mid])
{
left = mid +1;
}
else return mid;
}
}
如果我们使⽤递归的做法，程序如下
int C_binaryfindvalue(Seqlist&seq,const elemtype val,int left,int right)
{
if(left < right)
{
return error;
}
int mid =(right - left +1)/2+ left;
if(val < seq.data[mid])
{
mid=C_binaryfindvalue(seq, left, mid -1, val);
}
else if(val > seq.data[mid])
{
mid=C_binaryfindvalue(seq, mid+1, right, val);
}
else
{
while(mid>left&&seq.data[mid]== seq.data[mid -1])//这样是如果数据中存在多个重复的数，需要输出第⼀位时的操作{
mid--;
}
}return mid;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。