Chapter #5 – Recursion

An activation record usually contains:

  • Values for all parameters to the function, location of the first cell in an array is passed or a variable is passed by reference, and copes of all other data.
  • Local (automatic) variables that can be stored elsewhere, in which case, the activation record contains only their descriptors and pointers to the locations where they are stored.
  • The return address to resume control by the caller, the address of the caller’s instruction immediately following the call.
  • The returned value for a function not declared as a void.

Advantages of using recursion:

  1. Similarity to the original definition.
  2. Increases the program readability.
  3. Improves self-documentation.
  4. Simplifies coding.
  5. Shorter than iterative implementations.

Tail recursion is characterized by the use of only one recursive call at the very end statement left to be executed by the function; the recursive call is not only the last statement but there are no earlier recursive calls, direct or indirect.

Tail recursion is more suitable for language like Prolog that has no explicit loop construct.

Consider the following functions:

void
function1()

{

char
stack[80];

register
int
top = 0;

cin.get(stack[top]);

while(stack[top] != ‘\n’)

cin.get(stack[++top]);

for (top -=2; top >= 0; cout.put(stack[top–]));

}

void
function2()

{

stack<int> st;

int
ch;

cin.get(ch);

while(ch != ‘\n’)

{

st.push(ch);

cin.get(ch);

}

while(!st.empty())

cout.put(st.pop());

}

After comparing function1 to function2, we can conclude that the first version is better because it is faster, no function calls are made, and the function is self-sufficient, whereas, function2 calls at least one function during each loop iteration, slowing down execution.

Indirect recursion is defined as, when a function call itself indirectly. As example:

  • Function f() will call function g()
  • Function g() is going to call function f() again.

A more complicated case of recursion is found in definition in which a function is not only defined in terms of itself, but also as one of the parameters. This is called Nested Recursion.

If you traced a usual funtion that computes Fibonacci Numbers, you’ll observe that it repeats computation of some numbers. As indicated using recursion Fib(n), number of computations equals to 2 . Fib(n + 1) – 1.

A better solution is done by using the equation: Fib(n) = dn/root(5) where d = 1/2 +(1 + root(5)). This is coded as:

unsigned int
deMoivreFib(unsigned int n)

{

return ceil(exp(n*log(1.6180339897) – log(2.2360697995)) – .5);

}

Download solutions for this chapter from this link

One thought on “Chapter #5 – Recursion

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s