
Introduction to RecursionHi! So you're all set to dive into recursive programming. Well, this page is about the basics. The definition. The meaning. And a small cute example. I assume that you have a fair knowledge of one of the languages: C, C++, Pascal, etc. which supports recursion.
First the formalities. Meaning of Recursion. You may skip it if you already know what the concept is.

RecursionIn normal procedural languages, one can go about defining
functions and procedures, and 'calling' these from the 'parent' functions.
I hope you already know that. FactorialFactorial is a mathematical term. Factorial of a number,
say n, is equal to the product of all integers from 1 to n. Factorial
of n is denoted by n! = 1x2x3...x n. The simplest program to calculate factorial of a number is a loop with a product variable. Instead, it is possible to give a recursive definition for Factorial as follows: 1) If n=1, then Factorial of n = 1 2) Otherwise, Factorial of n = product of n and Factorial of (n1) Check it out for yourself; it works. The following code
fragment (in C) depicts Recursion at work. int Factorial(int n) { if (n==1) 
The important thing to remember when creating a recursive
function is to give an 'endcondition'. We don't want the function
to keep calling itself forever, now, do we? Somehow, it should know when
to stop. There are many ways of doing this. One of the simplest is by
means of an 'if condition' statement, as above. In the above example,
the recursion stops when n reaches 1. In each instance of the function,
the value of n keeps decreasing. So it ultimately reaches 1 and ends.
Of course, the above function will run infinitely if the initial value
of n is less than 1. So the function is not perfect. The Imagination is a very hard thing. Imagination of Recursion is all the more tricky. Think of clones. Say you have a machine to make clones of yourself, and (for lack of a better passtime) decide to find the factorial of a number, say 10, using your clones. So, being smart, this is what you do: First, there's only You. Let's call you You1.
You have the number 10 in your pocket. Being smart, you know that all
you need to find the factorial of 10 ( You2 is (you guessed it) just as smart as you! He tucks his number (9) into his pocket, turns on the machine, and out pops a clone (You3). The new clone is given the job of 8factorial, which it proceeds to do while (unbeknownst to you) You2 is sipping on his own glass of lemonade on his own sofa. And so the story goes on until finally one fine day... Out pops You10 who is given strict instructions (by You9) to get the factorial of 1. Now, You10, being just as smart as any of the other you's, knows very well that the factorial of 1 is... 1. So he says to You9 (who was just about to doze off on his sofa), "Here's your factorial of 1." You9 snatches the result from his subordinate You10, takes out his plasma gun, and zaps You10 out of existence. He scribbles on a piece of paper, calculating the product of the value he got from You10 with the number in his pocket, 2. "Heh, heh, heh" he thinks, and goes to his boss, You8, saying,"Here's your factorial of 2..." ...blah...blah... and finally You2 wakes you up from your slumber, and says to you, "Here's your factorial of 9" You zap him off, multiply by the 10 in your pocket, and There You Have It !! Now, wasn't that simple? Here, 'You' were the function. The 'clones' are merely new instances of the same function. They all think and act alike. At one point, there are 10 You's (which occupies a lot of memory space). As soon as an instance returns a value and finishes its job, it is zapped off from memory. Recursion can get much, much trickier than that  get your fundas right.

ExercisesHere are some programs for you to try... but since nobody these days actual works out the problems, all I'm going to ask you to do is give each problem a thought. You should be able to solve them all. 1. Write a function using Recursion to print numbers from n to 0. 2. Write a function using Recursion to print numbers from 0 to n. (You just need to shift one line in the program of problem 1.) 3. Write a function using Recursion to enter and display a string in reverse. Don't use arrays/strings. 4. Write a function using Recursion to enter and display a string in reverse and state whether the string contains any spaces. Don't use arrays/strings. 5. Write a function using Recursion to check if a number n is prime. (You have to check whether n is divisible by any number below n) 6. Write a function using Recursion to enter characters one by one until a space is encountered. The function should return the depth at which the space was encountered.

recursion
index introduction
magic
squares tic
tac toe connect
4 optimizing recursion trees sorting equation generator other problems 

home jokes programming about me resume guest book  