marq

Dr. Charles Simonyi is the Father of Modern Microsoft Excel                                           JavaScript was originally developed by Brendan Eich of Netscape under the name Mocha, later LiveScript, and finally renamed to JavaScript.                                           The word "Biology" is firstly used by Lamarck and Treviranus                                           Hippocrates (460-370 bc) is known as father of medicine.                                           Galene, 130-200 is known as father of Experimental Physology                                           Aristotle (384-322 BC) is known as Father of Zoology because he wrote the construction and behavior of different animals in his book "Historia animalium"                                           Theophrastus(370-285 BC) is known as father of Botany because he wrote about 500 different plants in his book "Historia Plantarum".                                           John Resig is known as Father of Jquery -                                          HTML is a markup language which is use to design web pages. It was invented in 1990 by Tim Berners-Lee.                                                                The Google was founded by Larry Page and Sergey Brin.                                                                Rasmus Lerdorf was the original creator of PHP. It was first released in 1995.                                                               Facebook was founded by Mark Zuckerberg                                                               Bjarne Stroustrup, creator of C++.                                                                Dennis Ritchie creator of C                                                                                                                              James Gosling, also known as the "Father of Java"                                          At 11.44%, Bihar is India's fastest growing state                                          Father of HTML -Tim Berners Lee                                          orkut was created by Orkut Büyükkökten, a Turkish software engineer                    Photoshop: It came about after Thomas Knoll, a PhD student at the University of Michigan created a program to display grayscale images on a monochrome monitor which at the time was called 'Display'.

recursion



A function can call itself. This is called recursion, and recursion can be direct or indirect. It is direct when a function calls itself; it is indirect recursion when a function calls another function that then calls the first function.




Some problems are most easily solved by recursion, usually those in which you act on data and then act in the same way on the result. Both types of recursion, direct and indirect, come in two varieties: those that eventually end and produce an answer, and those that never end and produce a runtime failure. Programmers think that the latter is quite funny (when it happens to someone else).
It is important to note that when a function calls itself, a new copy of that function is run. The local variables in the second version are independent of the local variables in the first, and they cannot affect one another directly, any more than the local variables in main() can affect the local variables in any function it calls, as was illustrated in Listing 5.4.



Factorial 


#include <iostream.h>
#include <conio.h>
int factorial(int);


void main(void) {
int number;

cout << "Please enter a positive integer: ";
cin >> number;
if (number < 0)
cout << "That is not a positive integer.\n";
else
cout << number << " factorial is: " << factorial(number) << endl;
getch();
}


int factorial(int number) {
int temp;


if(number <= 1) return 1;


temp = number * factorial(number - 1);
return temp;
}



To illustrate solving a problem using recursion, consider the Fibonacci series:
1,1,2,3,5,8,13,21,34...
Each number, after the second, is the sum of the two numbers before it. A Fibonacci problem might be to determine what the 12th number in the series is.
One way to solve this problem is to examine the series carefully. The first two numbers are 1. Each subsequent number is the sum of the previous two numbers. Thus, the seventh number is the sum of the sixth and fifth numbers. More generally, the nth number is the sum of n - 2 and n - 1, as long as n > 2.
Recursive functions need a stop condition. Something must happen to cause the program to stop recursing, or it will never end. In the Fibonacci series, n < 3 is a stop condition.
The algorithm to use is this:
1. Ask the user for a position in the series.
2.
 Call the fib() function with that position, passing in the value the user entered.
3. 
The fib() function examines the argument (n). If n < 3 it returns 1; otherwise, fib() calls itself (recursively) passing in n-2, calls itself again passing in n-1, and returns the sum.
If you call fib(1), it returns 1. If you call fib(2), it returns 1. If you call fib(3), it returns the sum of calling fib(2) and fib(1). Because fib(2) returns 1 and fib(1) returns 1fib(3) will return2.
If you call fib(4), it returns the sum of calling fib(3) and fib(2). We've established that fib(3)returns 2 (by calling fib(2) and fib(1)) and that fib(2) returns 1, so fib(4) will sum these numbers and return 3, which is the fourth number in the series.
Taking this one more step, if you call fib(5), it will return the sum of fib(4) and fib(3). We've established that fib(4) returns 3 and fib(3) returns 2, so the sum returned will be 5.
This method is not the most efficient way to solve this problem (in fib(20) the fib() function is called 13,529 times!), but it does work. Be careful: if you feed in too large a number, you'll run out of memory. Every time fib() is called, memory is set aside. When it returns, memory is freed. With recursion, memory continues to be set aside before it is freed, and this system can eat memory very quickly. Sample program below implements the fib() function.

#include <iostream.h>

int fib(int n);

int main()
{

int n, answer;
cout << "Enter number to find: ";
cin >> n;
cout << "\n\n";

      answer = fib(n);
      cout << answer << " is the " << n << "th Fibonacci number\n";
         return 0;
    }

    int fib (int n)
    {
      cout << "Processing fib(" << n << ")... ";

      if (n < 3 )
      {
         cout << "Return 1!\n";
         return (1);
      }
 else
      {
       cout << "Call fib(" << n-2 << ") and fib(" << n-1 << ").\n";
       return( fib(n-2) + fib(n-1));
    } 

    }



Analysis: The program asks for a number to find on line 15 and assigns that number to target. It then calls fib() with the target. Execution branches to the fib() function, where, on line 28, it prints its argument.
The argument n is tested to see whether it equals 1 or 2 on line 30; if so, fib() returns. Otherwise, it returns the sums of the values returned by calling fib() on n-2 and n-1.
In the example, n is 5 so fib(5) is called from main(). Execution jumps to the fib() function, andn is tested for a value less than 3 on line 30. The test fails, so fib(5) returns the sum of the values returned by fib(3) and fib(4). That is, fib() is called on n-2 (5 - 2 = 3) and n-1 (5 - 1 = 4).fib(4) will return 3 and fib(3) will return 2, so the final answer will be 5.
Because fib(4) passes in an argument that is not less than 3, fib() will be called again, this time with 3 and 2. fib(3) will in turn call fib(2) and fib(1). Finally, the calls to fib(2) and fib(1)will both return 1, because these are the stop conditions.
The output traces these calls and the return values. Compile, link, and run this program, entering first 1, then 2, then 3, building up to 6, and watch the output carefully. Then, just for fun, try the number 20. If you don't run out of memory, it makes quite a show!

Recursion is not used often in C++ programming, but it can be a powerful and elegant tool for certain needs.


No comments:

Post a Comment