用棧實現遞歸函數的一個例子(C語言實現)

用棧實現遞歸函數的一個例子(C語言實現)

#include <stdio.h>
#include <stdlib.h>
void *MemAlloc(unsigned int ulMemSize)
{
return malloc(ulMemSize);
}
void MemFree(void **ppvFree)
{
free(*ppvFree);
*ppvFree = 0;
}
/* 裴波那契數列非遞歸實現 */
/* 棧元素內存可以優化，在此不做優化， 僅僅供學習參考 */
unsigned int FibnoFunction(unsigned int ulNum)
{
unsigned int *pulStackBt;
unsigned int *pulStackTop;
unsigned int ulSumRet;
pulStackBt = MemAlloc(sizeof(unsigned int)*(ulNum+ 1));
if (pulStackBt == 0)
{
return -1;
}
/* 初始化棧 */
pulStackTop = pulStackBt + ulNum;
pulStackTop[0] = 0;
if (ulNum > 0)
{
pulStackTop[-1] = 1;
}
/* 依次出棧 */
while (pulStackTop > pulStackBt + 1)
{
pulStackTop[-2] = pulStackTop[-1] + pulStackTop[0];
pulStackTop--;
}
ulSumRet = *pulStackBt;
MemFree(&pulStackBt);
return ulSumRet;
}
int main(int args, unsigned char **ppargs)
{
unsigned int ulFebSum = 0;
for (ulFebSum = 0; ulFebSum < 15; ulFebSum++)
{
printf("FibnoFunction(%u) = %u\r\n", ulFebSum, FibnoFunction(ulFebSum));
}
return 0;
}