（3.1）递归与分支之递归

本文主要是介绍（3.1）递归与分支之递归，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.递归的定义

• 递归：
  子程序（或函数） 直接调用自己或通过一系列调用语句间接调用自己，称为递归。
  递归是一种描述问题和解决问题的基本方法。
• eg：函数A中的语句直接调用了函数A本身，这叫做直接递归调用。

void A()
{ …A();…
}

• eg：间接递归调用

void B()
{...C();...
}void C()
{...B();...
}

2.递归的基本思想

• 问题分解
• 递归的要素：
  ⑴ 递归边界条件：确定递归到何时终止，也称为递归出口；
  ⑵ 递归模式：大问题是如何分解为小问题的，也称为递归体。

3.应用eg

• eg：阶乘函数
  

递归算法
int fact ( int n )
{if ( n == 0 ) //边界条件return 1;else return n * fact (n-1);//递推关系式
}

• 求解阶乘 n! 的过程
  

• 递归过程与递归工作栈
  （1）递归过程在实现时，需要自己调用自己。
  （2）层层向下递归，返回次序正好相反：
  （3）通过栈知道，函数调用就是通过栈来返回地址和参数传递的过程，因为他参数传递是用地址保存的；
  递归也是通过栈来实现参数传递和他的解的值的传递
  

• eg：使用非递归算法
  能不用递归，就不用递归；
  利用栈来实现非递归的算法，来提高效率；
  不少递归问题就是尾递归，可以不借助栈，直接改成循环，效率高些；
  写成递归形式，就是好看，容易理解；
  

非递归算法
int fact ( int n )
{int f=n;while(--n>=1)//循环实现递归调用，避免使用递归，这里就是尾递归的方式f*=n;return f;
}

4.递归与尾递归(非递归形式)

• eg1：Fibonacci数列求解.
  

递归求解:
int f (int n)
{if (n<=1)return (n);elsereturn (f(n-1)+f(n-2));//递归关系式是作为return返回的，所以他是尾递归，所以可以改成循环语句，
}非递归求解，即：尾递归
int f(int n)
{ //pre:前一次Fibc的值；//now：现在Fibc的值；//next：下一次Fibc的值；int pre, now, next, j;if (n<=1) return (n);else{ pre=0;now=1;for(j=2;j<=n;j++){ next=pre+now;pre=now;now=next;}return(next);//j=n时，就是最终的解，直接return}
}

• eg2：回文串
  如果一个字符串从左向右读和从右向左读完全相同 （不区分大小写），则这个字符串称为回文串（palindrome)，例如“noon” 、“madam” 等都是回文串。
  （1）递归思路
  
  （2）非递归思路，即尾递归思路
  

递归方法：
bool palindrome(string &s,unsigned h,unsigned t)//h:字符串的起始地址，t：字符串的结束地址
{if (h>=t) //S是空串或长度为1return 1;if(tolower(s[h])==tolower(s[t]))//tolower都转换成小写return palindrome(s,h+1,t-1);//这里递归关系只在return的时候存在，也就是说这是尾递归，可以改成循环elsereturn 0;//返回是不是回文串
}
尾递归方法：
bool palindrome(string &s)
{int h=0,t=strlen(s)-1;while (h<=t){if (totlower(s[h])!=tolower(s[t]))return 0;else{h++;t--;}}return 1;
}

这篇关于（3.1）递归与分支之递归的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---