3rd-learnings of the week(Colegado)

RECURSION

The repetitive process by which a functions calls itself is called recursion or circular definition. This is a way of defining something in terms of itself. A function is said to be recursive if a statement in the body of the function calls the function that contains it.


Base Case. This is the part of the recursive function that is found on the if clause. This contains the condition that should be satisfied at one point of execution to terminate the repetitive process done by the recursive function.
General Case. This is the part of the recursive function that is found on the else-clause. This contains the function call of the recursive function to itself.

Give the output of the ff. program when the value entered for a=5.
#include
main()
{
int a, b;
clrscr();
printf(“Enter a value:”);
scanf(“%d”, &a);
b= solve (a);
printf(“The new value is %d”, b);
getch();

solve (int a)
{
if (a == 1) return 2;
else return (solve (a-1) + 2);
}


The output is:

Enter a value: 5
The new value is 10.

Direct and Indirect Recursion

Direct recursions are recursive functions that can call itself through a function call directly inside the body of the function. Indirect recursions are recursive functions that can call another functions outside its function.

A common method of simplification is to divide a problem into subproblems of the same type. As a computer programming technique, this is called divide and conquer and is key to the design of many important algorithms, as well as being a fundamental part of dynamic programming.

Recursion in computer programming is exemplified when a function is defined in terms of itself. One example application of recursion is in parsers for programming languages. The great advantage of recursion is that an infinite set of possible sentences, designs or other data can be defined, parsed or produced by a finite computer program.

Recurrence relations are equations to define one or more sequences recursively. Some specific kinds of recurrence relation can be "solved" to obtain a non-recursive definition.

A classic example of recursion is the definition of the factorial function, given here in C code:

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

The function calls itself recursively on a smaller version of the input (n - 1) and multiplies the result of the recursive call by n, until reaching the base case, analogously to the mathematical definition of factorial.

Use of recursion in an algorithm has both advantages and disadvantages. The main advantage is usually simplicity. The main disadvantage is often that the algorithm may require large amounts of memory if the depth of the recursion is very large. It has been claimed that recursive algorithms are easier to understand because the code is shorter and is closer to a mathematical definition, as seen in these factorial examples.

It is often possible to replace a recursive call with a simple loop, as the following example of factorial shows:

unsigned int factorial(unsigned int n) {
if (n <= 1) return 1;
unsigned int result = n;
while (--n) result *= n;
return result;
}

It should be noted that on most CPUs the above examples give correct results only for small values of n, due to arithmetic overflow.

An example of a recursive algorithm is a procedure that processes (does something with) all the nodes of a tree data structure:

void ProcessTree(node x) {
unsigned int i = 0;
while (i < x.count) {
ProcessTree(x.children[i]);
i++;
}
ProcessNode(x); // now perform the operation with the node itself
}

To process the whole tree, the procedure is called with a root node representing the tree as an initial parameter. The procedure calls itself recursively on all child nodes of the given node (i.e. sub-trees of the given tree), until reaching the base case that is a node with no child nodes (i.e. a tree having no branches known as a "leaf").

A tree data structure itself can be defined recursively (and so predestinated for recursive processing) like this:

typedef struct {
unsigned int count;
node* children;
} node