回溯和尾递归

        最近，了解回溯的算法思想。

        个人认为，回溯的核心思想就是，类似枚举的，把所有的可能情况都遍历一遍，进行试探，在递归当中夹杂一些特定的判断，进行筛选，解决问题。再设计递归出口（回溯点），再回溯回来的时候，把原来改变的状态，改变过来。保持原样。

public static void numergodic(char [] data, int k)

{     

if(k == data.length){                                          // 回溯点

s = String.valueOf(data);                                  //把字符数组转化为字符串

set.add(s);

}

for(int i = k; i < data.length; i++){                          // k表示 当前要交换的位置,从第K个一直交换到最后一个

{ char t = data[k]; data[k] = data[i]; data[i] = t; }      // 试探

numergodic(data,k+1);

{ char t = data[k]; data[k] = data[i]; data[i] = t; }      // 回溯回来

}

}

       至于，尾递归呢。当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时，栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。前提是函数的结束部位返回结果。然后，把本次调用函数计算出来的结果值，传给下一次调用的函数。这样写，不会造成栈的溢出（理论上）。但是目前，很多编程语言，对于尾递归还是没有优化，会造成栈的溢出。

        线性递归：

对于线性递归, 它的递归过程如下:

Rescuvie(5)

{5 * Rescuvie(4)}

{5 * {4 * Rescuvie(3)}}

{5 * {4 * {3 * Rescuvie(2)}}}

{5 * {4 * {3 * {2 * Rescuvie(1)}}}}

{5 * {4 * {3 * {2 * 1}}}}

{5 * {4 * {3 * 2}}}

{5 * {4 * 6}}

{5 * 24}

120

        尾递归：

对于尾递归, 它的递归过程如下:

TailRescuvie(5)

TailRescuvie(5, 1)

TailRescuvie(4, 5)

TailRescuvie(3, 20)

TailRescuvie(2, 60)

TailRescuvie(1, 120)

120