ALevel-CS Chapter 24 Recursion

24.01 Concept of recursion

Key Terms

Recursive routine - a function or procedure defined in terms of itself
Base case - an explicit solution to a recursive function
General case - a definition of a recursive function in terms of itself

Concept of recursion

Recursive solutions have a base case and a general case. The base case gives a result without involving the general case. The general case is defined in terms of the definition itself. It is very important that the general case must come closer to the base case with each recursion, for any starting point.

24.02 Programming a recursive subroutine

递归代码的思路

以Factorial阶层函数为例

第一步 - 明确你的函数的功能

先明确的搞清楚函数到底是用来做什么的，函数的主要功能。函数需要传入一个阶层的数。

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER 

ENDFUNCTION

第二步 - 寻找递归结束条件

所谓递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，不然的话，会一直调用自己，进入无底洞。也就是说，我们需要找出当参数为啥时，递归结束，之后直接把结果返回。

阶层函数计算到最后一个1为止

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER 
    IF n = 0
        THEN 
            Result ← 1   // This is the base case
    ENDIF 
ENDFUNCTION

第三步 - 找出函数的等价关系式

第三步我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。要找到一个等价关系式，每次都可以直接使用等价调用。

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0
        THEN 
            Result ← 1   // This is the base case
        ELSE
            Result ← n * Factorial(n – 1) // This is the general case
    ENDIF 
    RETURN Result
ENDFUNCTION

什么是递归

进一步剖析「递归」，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决，子问题再拆解成子子问题，...，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,....,直到最开始的问题解决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的「递」和「归」。

在书上的例子上，我们把递称为 base case，归称为 Recursive。

Coding the factorial function

loop program:

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER 
    Result ← 1
    FOR i ← 1 TO n
        Result ← Result * i 
    NEXT i 
    RETURN Result 
ENDFUNCTION

denfine the function Factorial recursively

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0
        THEN 
            Result ← 1   // This is the base case
        ELSE
            Result ← n * Factorial(n – 1) // This is the general case
    ENDIF 
    RETURN Result
ENDFUNCTION

A recursive subrouting must:

hava a base case
have a general case
reach the base case after a finite (limited) number of calls to itself

24.03 Tracing a recursive subroutine

Tracing a recursive procedure

PROCEDURE CountUpTo(n : INTEGER) 
    IF n > 0 
        THEN 
            CALL CountUpTo(n – 1) 
    ENDIF 
    OUTPUT n 
ENDPROCEDURE

trace table

Note that the statements after CALL CountUpTo(n – 1) are not executed until control returns to this statement as the recursive calls unwind.

Tracing a recursive function

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0
        THEN 
            Result ← 1 
        ELSE 
            Result ← n * Factorial(n – 1) 
    ENDIF 
    RETURN Result 
ENDFUNCTION

24.04 Running a recursive subroutine

PROGRAM

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
    IF n = 0
        THEN 
            Result ← 1 
        ELSE
            Result ← n * Factorial(n - 1) 
    ENDIF 
    RETURN Result 
ENDFUNCTION

// main program

DECLARE Answer : INTEGER 
Answer ← Factorial(3) 
OUTPUT Answer

ENDPROGRAM

24.05 Benefits and drawbacks of recursion

Recursive solutions are often more elegant and use less program code than iterative solutions. However, repeated recursive calls can carry large amounts of memory usage and processor time

辅助阅读

一文看懂什么递归（算法小结）

为什么你学不会递归？告别递归，谈谈我的一些经验