[RA] Ch7 Recursion

Reading Assignment: All of Programming Ch7 Recursion

Besides iteration, we have another way to repeat the steps until appropriate conditions are met, namely recursion.

Reading Recursive Code

There is an example of factorial function.

int factorial(int n) {
    if(n <= 0) {
    	 return 1;
    }
    return n * factorial(n-1);
}

Writing Recursive Functions

One key difference is that the first function was obtained by following the Steps to write a program, and the recursive call corresponded to something we actually did in trying to solve the porblem. The second difference is that the factorial function has a base case –a condition in which it can give an other without calling itself. Another important aspect of the correct factorial function is that the recursive calls always make progress towards the base case.

The example of fib() is given here to illustrate the recursion.

Tail Recursion

In tail recursion, the recursive call is the last thing the function does before returning. That is, for a tail recursive function f, the only recursive call will be found in the context of return f(...);. A generalization of this idea is a tail call–a function call is a tail call if the caller returns immediately after the called function returns, without further computation. To understand this definition, the implementation of the factorial function is given below:

int factorial_helper(int n, int ans) {
    // base case
    if(n <= 0) {
    	 return ans;
    }
    // recursive call is a tail call

    // after recursive call returns, just return its answer.
    return factorial_helper(n - 1, ans * n);
}
int factorial(int n){
    return factorial(n, 1);
}

factorial_helper is a helper function that our primary function calls to do much of the work. Helper functions are quite common with tail recursion, but may appear in other contexts as well.

In fact, tail recursion and iteration are equivalent. Any algorithm we can write with iteration, we can trivially transform into tail recursion, and vice-versa. A smart compiler will compile tail recursive code and iterative code into the exact same instructions.

Functional Programming

In a purely functional language, you cannot actually modify a value once you create it(at least not from the standpoint of the language: the compiler is free to re-use the same “box” if it can conclude that you will never use it again). As such, there are not loops(which typically require modifying variables to change the conditions), but rather only recursive functions. What you would typically write as a loop, you instead just write as a tail recursive function.

Mutual Recursion

Mutual recursion is two or more functions which call each other.

int isOdd(int x) {
    if (x == 0) { return 0; }
    if (x == 1) { return 1: }
    return isEven(x-1);
}
int isEven(int x) {
    if(x == 0) { return 1; }
    if(x == 1) { return 0; }
    return isOdd(x-1);
}

There are many important uses of mutually recursive functions. One common use is recursive descent parsing. Parsing is the process of analyzing input text to determine its meaning.

Theory

Recursion has a strong relationship to the mathematical proof technique of induction. In fact, if we wanted to prove that a recursive function is correct, we would proceed by indction–and the structure of the inductive proof would mirror the structure of the recursive function.

In general, we can recurse on any set with a well-ordering(that is, a total ordering where every subset of the set has a least element) on it.