非递归算法？

一、非递归算法？

　　既然是非递归算法，我们自然要借助栈。那么关键就是确定什么时候进行入栈，访问、出栈这几个动作。

　　整个中序递归遍历的思路理解起来并不难，他和我们手动用 LNR 写出中序遍历的思路很相近：

　　 　　入栈：结点非空时，结点进栈，往左走；

　　 　　访问：栈非空，每出栈一个结点，便访问并往右走；

二、任何递归算法都有递归出口？

      递归就是方法里调用自身。

      在使用递归时，必须有一个明确的递归结束条件，称为递归出口。

         递归算法解题通常显得很简洁，但递归算法解题的运行效率较低，所以一般不提倡用递归算法设计程序。（用递归能实现的用循环也能实现）

       在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序

三、回溯算法是递归算法吗？

递归是一种算法结构，回溯是一种算法思想。

一个递归就是在函数中调用函数本身来解决问题。

回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”，意思就是对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1，2，3，4，5，我要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3 的时候发现和已经大于预期，那么4，5肯定也不行，这就是一种对搜索过程的优化。

四、中序递归算法？

中序遍历递归：左，根结点，右

先序遍历：根节点，左，右

后序：左，右，根

五、hanoi塔递归算法？

Hanoi Tower的递归算法实现思想为(假设盘数为N)

1）当A只有一个盘时(即N = 1)，直接将盘移动到C

2）当A中有两个或者两个以上的盘时(即N >=2)，先递归地将N-1个盘从塔A移到辅助塔B，再将剩下的一个盘从塔A移到塔C最后递归地将N-1个盘从塔B移到塔C

六、连通成分递归算法？

递归算法（recursionalgorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。

绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。

计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如Scheme）中习惯用递归来实现循环。

七、一般递归算法比非递归算法慢吗？

递归调用本身需要使用系统栈,每次分配函数内存以及栈都需要时间.不过这个过程耗时并不多,可以说,单纯的递归本身并不比非递归慢多少.

然而,实践中就会发现,递归处理部分问题,特别是递推类问题时会表现出效率极低.这个问题的出现是因为重复计算.

举例说,用递归求解斐波那契数列的第n项,一般的递归公式为

f(n) = f(n-1)+f(n-2)

f(2) = 1

f(1) = 1

请尝试模拟计算机运行这个递归,你会发现,其中的某一项f(x)并不是只算了一次.当你计算f(5)的时候,你会试图计算f(4)和f(3),然而在你计算f(4)的时候其实也要计算f(3),这样f(3)就被调用了两次.

想象这个过程是指数型扩展的,效率会随着n的增大极快地下降.

要解决这个问题,可以使用记忆化思想.

定义记忆数组r,函数体改为:

define f(n):

if r[n] is defined, then simply return r[n] as the answer.

else, f(n) = f(n-1) + f(n-2)

before return the value, take it down in r[n].

如此改进之后的递归函数效率上与递推算法相差无几

八、汉诺塔递归算法？

1 // 汉诺塔

2 # include <stdio.h>

3 void hanoi ( int n, char a, char b, char c ) //这里代表将a柱子上的盘子借助b柱子移动到c柱子

4 { if (1 == n) //如果是一个盘子直接将a柱子上的盘子移动到c

5 {

6 printf("%c-->%c\n",a,c);

7 }

8 else

9 {

10 hanoi ( n-1, a, c, b ) ; //将a柱子上n-1个盘子借助c柱子，移动到b柱子

11 printf("%c-->%c\n",a , c) ; //再直接将a柱子上的最后一个盘子移动到c

12 hanoi ( n-1, b, a, c ) ; //然后将b柱子上的n-1个盘子借助a移动到c

13 }

14 }

15 int main ()

16 { int n ;

17 printf( "Input the number of diskes:") ;

18 scanf("%d",&n) ;

19 hanoi ( n, 'A' , 'B' , 'C' ) ;

20 return 0;

21 }

复制代码

九、全排列递归算法详解？

全排列递归算法是一种用于生成所有可能的排列的算法。它基于这样的思想：对于一个包含n个元素的集合，第一个元素有n种选择，第二个元素有n-1种选择，依次类推。因此，总共有n!种可能的排列。该算法的递归实现方法是：对于给定的集合，首先选择第一个元素，然后对剩余的集合执行全排列递归算法。如此重复，直到所有可能的排列都被生成。

十、递归算法经典实例？

递归算法是一种用于解决复杂问题的算法，它通过重复调用自身来解决问题，它的基本思想是将一个复杂的问题分解成一系列的相对简单的子问题，然后逐个解决子问题，最终得到最终的解决方案。经典实例有汉诺塔问题、快速排序算法、二叉树的遍历算法、求解斐波那契数列等。

顶一下

(0)

0%

踩一下

(0)

0%