Answers and Solutions

Answer

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages do not define any looping constructs but rely solely on recursion to repeatedly call code. Computability theory proves that these recursive-only languages are Turing complete; they are as computationally powerful as Turing complete imperative languages, meaning they can solve the same kinds of problems as imperative languages even without iterative control structures such as “while” and “for”.

Stack Data Structure is used.

Answer

Recursion:

A method where the solution to a problem depends on solutions to smaller instances of the same problem. Each problem is considered to be set of similar smaller problems.

Stack Data Structure is used

Answer

Recursive functions

Many mathematical functions can be defined recursively:

• factorial
• Fibonacci
• Euclid's GCD (greatest common denominator)
• Fourier Transform

Many problems can be solved recursively, eg games of all types from simple ones like the Towers of Hanoi problem to complex ones like chess. In games, the recursive solutions are particularly convenient because, having solved the problem by a series of recursive calls, you want to find out how you got to the solution. By keeping track of the move chosen at any point, the program call stack does this housekeeping for you! This is explained in more detail later.

3.4.2 Example: Factorial

One of the simplest examples of a recursive definition is that for the factorial function:

factorial( n ) = if ( n = 0 ) then 1 else n * factorial( n-1 )

A natural way to calculate factorials is to write a recursive function which matches this definition:

function fact( int n ) { if ( n == 0 ) return 1; else return n*fact(n-1); }

Note how this function calls itself to evaluate the next term. Eventually it will reach the termination condition and exit. However, before it reaches the termination condition, it will have pushed n stack frames onto the program's run-time stack.

The termination condition is obviously extremely important when dealing with recursive functions. If it is omitted, then the function will continue to call itself until the program runs out of stack space - usually with moderately unpleasant results!

Failure to include a correct termination condition in a recursive function is a recipe for disaster!

Another commonly used (and abused!) example of a recursive function is the calculation of Fibonacci numbers. Following the definition:

fib( n ) = if ( n = 0 ) then 1 if ( n = 1 ) then 1 else fib( n-1 ) + fib( n-2 )

one can write:

function fib( int n ) { if ( (n == 0) || (n == 1) ) return 1; else return fib(n-1) + fib(n-2); }

Short and elegant, it uses recursion to provide a neat solution - that is actually a disaster! We shall re-visit this and show why it is such a disaster later.

Data structures also may be recursively defined. One of the most important class of structure - trees - allows recursive definitions which lead to simple (and efficient) recursive functions for manipulating them.