递归和尾递归递归和尾递归

原文
递归原理

递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用

你可能想知道如何实现调用自身的函数。诀窍在于，每当递归函数调用自身时，它都会将给定的问题拆解为子问题。递归调用继续进行，直到到子问题无需进一步递归就可以解决的地步。
为了确保递归函数不会导致无限循环，它应具有以下属性：

一个简单的基本案例（basic case）（或一些案例） —— 能够不使用递归来产生答案的终止方案。
一组规则，也称作递推关系（recurrence relation），可将所有其他情况拆分到基本案例。

注意，函数可能会有多个位置进行自我调用。
尾递归

尾递归函数是递归函数的一种，其中递归调用是递归函数中的最后一条指令。并且在函数中应该只有一次递归调用。

【递归和尾递归】尾递归的好处是，它可以避免递归调用期间栈空间开销的累积，因为系统可以为每个递归调用重用栈中的固定空间。
我们来看下面的例子:

public class Main {private static int helper_non_tail_recursion(int start, int [] ls) { if (start >= ls.length) { return 0; } // 不是尾递归，因为它在返回递归调用后进行了一些计算。 return ls[start] + helper_non_tail_recursion(start+1, ls); }public static int sum_non_tail_recursion(int [] ls) { if (ls == null || ls.length == 0) { return 0; } return helper_non_tail_recursion(0, ls); }//---------------------------------------------private static int helper_tail_recursion(int start, int [] ls, int acc) { if (start >= ls.length) { return acc; } // 这是一个尾递归，因为最后的指令是递归调用。 return helper_tail_recursion(start+1, ls, acc+ls[start]); }public static int sum_tail_recursion(int [] ls) { if (ls == null || ls.length == 0) { return 0; } return helper_tail_recursion(0, ls, 0); } }