理解递归函数最好的方法是掌握演绎推理,使用分治策略解决简单问题。虽然这种方法并不适用于所有递归问题,但适用于80%以上的递归情况。
基本上你需要发现递归方案的三个要素:
1. 一个演绎规则(或一组规则),将问题缩小为更小的问题。
2. 一组终止规则,设计得可以确保到达它们。
3. 某处用于保存中间结果的位置(通常是调用堆栈,有时是堆上的堆栈)。
为了举例说明,我们将使用我能想到的最愚蠢的例子,尝试计算字符串长度,通常你会使用while循环(假设你不使用系统库等)。
(pseudo code)
int length = 0;
while (current_char != newline) {
length = length + 1;
current_char = next_char;
}
递归策略就像
(pseudo logic)
The length of a string is one more than the length of a string with one less character
The length of the "" string is zero
(pseudo java code)
int recursive_length(String s) {
if (s.equals("")) {
return 0;
}
return 1 + recursive_length(s.substring(1))
}
对于 recursive_length 的调用,您的调用栈会像这样增长
recursive_length("hello");
这将被评估为
{1 + recursive_length("ello")}
该表达式的计算结果为
{1 + {1 + recursive_length("llo")} }
该表达式的结果为
{1 + {1 + {1 + recursive_length("lo")} } }
该表达式的值为
{1 + {1 + {1 + {1 + recursive_length("o")} } } }
评估结果为
{1 + {1 + {1 + {1 + {1 + recursive_length("")} } } } }
由于显式终止规则,现在它的计算结果为
{1 + {1 + {1 + {1 + {1 + {0}}}}}}
当我们从最内层的调用返回时,它被求值为
{1 + {1 + {1 + {1 + {1 + 0}}}}}
然后加法操作发生(最终)。
{1 + {1 + {1 + {1 + {1}}}}}
然后我们从那个调用中返回
{1 + {1 + {1 + {1 + {1 + 1}}}}
还有一个新增
{1 + {1 + {1 + {1 + {2}}}}}
以此类推
{1 + {1 + {1 + {1 + 2}}}}
{1 + {1 + {1 + {3}}}}
{1 + {1 + {1 + 3}}}
{1 + {1 + {4}}}
{1 + {1 + 4}}
{1 + {5}}
{1 + 5}
{6}
6
那么,所有这些中间的
1 + ...
是如何保留的呢?它们在调用栈中,随着我们评估下一个递归调用而退出。当内部调用返回时,代码会向上移动调用栈,累积答案。
由于递归非常依赖于堆栈,因此它自然适合某些类型的数据结构。唯一的问题是,如果算法出错,您永远无法达到终止状态,并且堆栈会不断增长。
为了解决这个问题,执行环境监视调用堆栈的进展,当感觉到堆栈太深时,就会使用
StackOverflow
错误中断程序。
在这个例子中,我在函数内部调用函数的事实是我正在使用递归。硬编码测试的早期退出条件是明显的终止规则。返回结果显然是归纳推理,将问题分解成更小的问题。
这意味着验证递归函数通常是一个逻辑问题,而不是一个编程问题。但有时候即使是最好的逻辑论证也会被编程错误所破坏 :)
跟踪执行过程中最重要的部分是记录各种堆栈中的状态。在本例中,我使用括号,但只要您有一种一致的方法来跟踪它们,使用什么符号都无所谓。