xml地图|网站地图|网站标签 [设为首页] [加入收藏]

【奥门金沙手机娱乐网址】一步一步写算法(之循环和递归)

时间:2019-11-15 00:08来源:计算机
【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing@163.com】      其实编程的朋友知道,不管学什么语言,循环和递归是两个必须学习的内容。当然,如果循环

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】

 

    其实编程的朋友知道,不管学什么语言,循环和递归是两个必须学习的内容。当然,如果循环还好理解一点,那么递归却没有那么简单。我们曾经对递归讳莫如深,但是我想告诉大家的是,递归其实没有那么可怕。所谓的递归就是函数自己调用自己而已,循环本质上也是一种递归。

    1)求和递归函数

    我们可以举一个循环的例子,前面我们说过,如果编写一个1到n的求和函数怎么写呢,你可能会这么写:

int calculate(int m) 

    int count = 0; 
    if(m <0) 
        return -1; 
 
    for(int index = 0; index <= m; index++) 
        count += index; 
     
    return count; 

int calculate(int m)
{
 int count = 0;
 if(m <0)
  return -1;

 for(int index = 0; index <= m; index++)
  count += index;
 
 return count;
}    上面只是一个示范。下面我们看看如果是递归应该怎么写呢?

int calculate(int m) 

    if(m == 0) 
        return 0; 
    else 
        return calculate(m -1) + m; 

int calculate(int m)
{
 if(m == 0)
  return 0;
 else
  return calculate(m -1) + m;
}    大家看着两段代码有什么不同?

    (1)第一段代码从0,开始计算,从0到m逐步计算;第二段代码是从10开始计算,逐步到0之后这回,这样同样可以达到计算的效果

    (2)第一段代码不需要重复的压栈操作,第二段需要重复的函数操作,当然这也是递归的本质

    (3)第一段代码比较长,第二段代码较短

 

    2)查找递归函数

    大家可能说,这些代码有些特殊。如果是查找类的函数,有没有可能修改成递归函数呢?

int find(int array[], int length, int value) 

    int index = 0; 
    if(NULL == array || 0 == length) 
        return -1; 
 
    for(; index < length; index++) 
    { 
        if(value == array[index]) 
            return index; 
    } 
 
    return -1; 

int find(int array[], int length, int value)
{
 int index = 0;
 if(NULL == array || 0 == length)
  return -1;

 for(; index < length; index++)
 {
  if(value == array[index])
   return index;
 }

 return -1;
}

    大家可能说,这样的代码可能修改成这样的代码:

int _find(int index, int array[], int length, int value) 

    if(index == length) 
        return -1; 
 
    if(value == array[index]) 
        return index; 
 
    return _find(index + 1,  array, length, value); 

 
int find(int array[], int length, int value) 

    if(NULL == array || length == 0) 
        return -1; 
 
    return _find(0, array, length, value); 

int _find(int index, int array[], int length, int value)
{
 if(index == length)
  return -1;

 if(value == array[index])
  return index;

 return _find(index + 1,  array, length, value);
}

int find(int array[], int length, int value)
{
 if(NULL == array || length == 0)
  return -1;

 return _find(0, array, length, value);
}

    3) 指针变量遍历

    结构指针是我们喜欢的遍历结构,试想如果有下面定义的数据结构:

typedef struct _NODE 

    int data; 
    struct _NODE* next; 
}NODE; 
typedef struct _NODE
{
 int data;
 struct _NODE* next;
}NODE;    那么,此时我们需要对一个节点链接中的所有数据进行打印,应该怎么办呢?大家可以自己先想想,然后看看我们写的代码对不对。

void print(const NODE* pNode) 

    if(NULL == pNode) 
        return; 
 
    while(pNode){ 
        printf("%dn", pNode->data); 
        pNode = pNode->next; 
    } 

void print(const NODE* pNode)
{
 if(NULL == pNode)
  return;

 while(pNode){
  printf("%dn", pNode->data);
  pNode = pNode->next;
 }
}
    那么此时如果改成递归,那就更简单了:

void print(const NODE* pNode) 

    if(NULL == pNode) 
        return; 
    else 
        printf("%dn", pNode->data); 
     
    print(pNode->next); 

void print(const NODE* pNode)
{
 if(NULL == pNode)
  return;
 else
     printf("%dn", pNode->data);
 
 print(pNode->next);
}
    其实,写这么多,就是想和大家分享一下我个人的观点:循环是一种特殊的递归,只有递归和堆栈是等价的。所有的递归代码都可以写成堆栈的形式,下面的一片博客我们就讨论一下堆栈和递归的关系。要想写好,必须熟练掌握堆栈。

声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 其实编程的朋友知道,不管学什么语言,循环和递归是...

编辑:计算机 本文来源:【奥门金沙手机娱乐网址】一步一步写算法(之循环和递归)

关键词: