RECURSION

This week we just tackled about RECURSION. Recursion defined as 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.

Parts of the Recursive function

☺ 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.

Example 1 (This Example was given to us by our TLE teacher, Mr. Ernie Balbuena )

factorial (int n)

{

if (n == 1 || n == 0) return 1;

else return (n * factorial (n-1));

}

If the n value is 4, 4 * (factorial (4-1)

if the n value is 3, 3 * (factorial (3-1)

if the n value is 2, 2 * (factorial (2-1)

if the n value is 1, 1

factorial (int n)

{

if (n == 1 || n == 0) return 1;

else return (n * factorial (n-1));

}

Simplifying the expression……

4 * (factorial (4-1) = 24 general case

3 * (factorial (3-1) = 6 general case

2 * (factorial (2-1) = 2 general case

1 base case

Therefore, the final return value when n=4 is 24.

Recursion

RECURSION

Recursion in computer science is a way of thinking about and solving problems. It is, in fact, one of the central ideas of computer science. Solving a problem using recursion means the solution depends on solutions to smaller instances of the same problem.

"The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."

Most high-level computer programming languages support recursion by allowing a function to call itself within the program text. Imperative languages define looping constructs like “while” and “for” loops that are used to perform repetitive actions. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory has proven that these recursive only languages are mathematically equivalent to the imperative languages, meaning they can solve the same kinds of problems even without the typical control structures like “while” and “for”.

• Recursion in computer science

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 <>

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

• Recursive programming

Creating a recursive procedure essentially requires defining a "base case", and then defining rules to break down more complex cases into the base case. Key to a recursive procedure is that with each recursive call, the problem domain must be reduced in such a way that eventually the base case is arrived at.

Some authors classify recursion as either "generative" or "structural". The distinction is made based on where the procedure gets the data that it works on. If the data comes from a data structure like a list, then the procedure is "structurally recursive"; otherwise, it is "generatively recursive".

Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. HTDP (How To Design Programs) refers to this kind as generative recursion. Examples of generative recursion include: gcd, quicksort, binary search, mergesort, Newton's method, fractals, and adaptive integration.

• Examples of Recursively defined procedures (generative recursion)

Factorial
A classic example of a recursive procedure is the function used to calculate the factorial of an integer.
Function definition: 0 \\ \end{cases} "

Pseudocode (recursive):
function factorial is:input: integer n such that n >= 1output: [n × (n-1) × (n-2) × … × 1]
1. if n is 0, return 1
2. otherwise, return [ n × factorial(n-1) ]
end factorial
A recurrence relation is an equation that relates later terms in the sequence to earlier terms.Recurrence relation for factorial:bn = n * bn-1b0 = 1
Computing the recurrence relation for n = 4:
b4 = 4 * b3 = 4 * 3 * b2
= 4 * 3 * 2 * b1
= 4 * 3 * 2 * 1 * b0
= 4 * 3 * 2 * 1 * 1
= 4 * 3 * 2 * 1
= 4 * 3 * 2
= 4 * 6
= 24

Example Implementations:
Scheme (recursive)
C (recursive)
;; Input: Integer n such that n >= 0
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
//INPUT: n is an integer such that n >= 0
int fact(int n)
{
if (n == 0)
return 1;
else
return n * fact(n - 1);
}

This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages:
Pseudocode (iterative):
function factorial is:input: integer n such that n >= 0output: [n × (n-1) × (n-2) × … × 1]
1. create new variable called running_total with a value of 1
2. begin loop
1. if n is 0, exit loop
2. set running_total to (running_total × n)
3. decrement n
4. repeat loop
3. return running_total
end factorial

Scheme, however, is a functional programming language and does not define any looping constructs. It relies solely upon recursion to perform all looping. Because Scheme is tail-recursive, a recursive procedure can be defined that implements the factorial procedure as an iterative process — meaning that it uses constant space but linear time.

Example implementations:
Scheme (iterative)
C (iterative)
;; Input: Integer n such that n >= 0
(define (fact n)
(fact-iter 1 n))
(define (fact-iter running_total n)
(if (= n 0)
running_total
(fact-iter (* running_total n) (- n 1))))
int fact(int n)
{
int running_total;
for (running_total = 1; n != 0; --n)
running_total *= n;
return running_total;
}

Fibonacci
Another well known recursive sequence is the Fibonacci numbers. The first few elements of this sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21...
Function definition: = 2 \\ \end{cases} "

Pseudocode
function fib is:
input: integer n such that n >= 0
1. if n is 0, return 0
2. if n is 1, return 1
3. otherwise, return [ fib(n-1) + fib(n-2) ]
end fib

Recurrence relation for Fibonacci:bn = bn-1 + bn-2b1 = 1, b0 = 0
Computing the recurrence relation for n = 4:
b4 = b3 + b2
= b2 + b1 + b1 + b0
= b1 + b0 + 1 + 1 + 0
= 1 + 0 + 1 + 1 + 0
= 3

Example Implementations:
Scheme
C
Python
;; n is an integer such that n >= 0
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else
(+ (fib (- n 1))
(fib (- n 2))))))
int fib(int n)
{
if (n == 0)
return 0;
else if (n == 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)

These implementations are especially bad because each time the function is executed, it will make two function calls to itself each of which in turn makes two more function calls and so on until they "bottom out" at 1 or 0. This is an example of "tree recursion", and grows exponentially in time and linearly in space requirements.

Recursion Learnings

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.

Parts of the Recursive function

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.

ILLUSTRATIVE EXAMPLE:

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);

}

OUTPUT:

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 Whole New Year... Whole New Excitement?

Scope of Variables in Function

In this C++ Tutorial you will learn about Scope of Variables in Function viz Local Variables - Scope of Local Variables, Global Variables - Scope of Global Variables.

The scope of the variables can be broadly be classified as

• Local Variables
• Global Variables

Local Variables:

The variables defined local to the block of the function would be accessible only within the block of the function and not outside the function. Such variables are called local variables. That is in other words the scope of the local variables is limited to the function in which these variables are declared.

Let us see this with a small example:

#include
int exforsys(int,int);
void main( )
{
int b;
int s=5,u=6;
b=exforsys(s,u);
cout<<”\n The Output is:”<

In the above program the variables x, y, z are accessible only inside the function exforsys( ) and their scope is limited only to the function exforsys( ) and not outside the function. Thus the variables x, y, z are local to the function exforsys. Similarly one would not be able to access variable b inside the function exforsys as such. This is because variable b is local to function main.

Global Variables:

Global variables are one which are visible in any part of the program code and can be used within all functions and outside all functions used in the program. The method of declaring global variables is to declare the variable outside the function or block.

For instance

#include
int x,y,z; //Global Variables
float a,b,c; //Global Variables
void main( )
{
int s,u; //Local Variables
float w,q; //Local Variables
……..
…………….
}

In the above the integer variables x, y and z and the float variables a, b and c which are declared outside the block are global variables and the integer variables s and u and the float variables w and q which are declared inside the function block are called local variables.

Thus the scope of global variables is between the point of declaration and the end of compilation unit whereas scope of local variables is between the point of declaration and the end of innermost enclosing compound statement.

Let us see an example which has number of local and global variable declarations with number of inner blocks to understand the concept of local and global variables scope in detail.

#include
int g;
void main( )
{
int a;
{
int b;
b=25;
a=45;
g=65;
}
a=50;
exforsys( );
}

void exforsys( )
{
g = 30; //Scope of g is throughout the program and so is used between function calls
}

Scope of b is till the first braces shaded as Yellow

Scope of a is till the end of main brace shaded as red