Recursive Program

[Butnud]

I have no idea what one is. In class I am trying to catch up but I am at a point where I need one. Can you make me a simple one so I can relate to it.
It won't be turned in, I have to make a recurvie program using some elements so the one you make won't do me any good but it refer to it.

Thank you!

[twanvl]

A recursive function is a function that calls itself.

Here is an example of a function that calculates the factorial (...x5x4x3x2x1) of a number:

int factorial(int iNumber){
    if (iNumber==0)
        return 1;
    else
        return factorial(iNumber-1);//this is what makes it recursive
} 

recursive functions are often much easier to write then functions with loops, and sometimes they are the only solution to a problem.
You must always beware that you don't end up in an infinite loop (resulting in a stack overflow)

[Butnud]

I am trying to compile the program to see how it works so i can create my own.

what is wrong with what I did

//Rob Gross
//3/13/02
//Recursive Program

void main()
{

int factorial(int iNumber){
if (iNumber==0)
return 1;
else
return factorial(iNumber-1);//this is what makes it recursive
}
}


[C:\Student Temp\recursive\recursive.cpp(8) : error C2601: 'factorial' : local function definitions are illegal]

This line is highlighted!
[int factorial(int iNumber){]

[twanvl]

You can't put one function inside another function. Here is an example of how it should be done (C++):

//This includes files needed for basic output to the screen
#include <iostream>
using namespace std;

//if the implementation of the function comes after the call, it needs to be declared first
int factorial(int iNumber);

//this is the application's main function
int main() 
{ 
    cout << "the factorial of 5 is: " << factorial(5); //call the function, and output to the screen
    return 0;
} 

//Calculates the factorial of a number
int factorial(int iNumber)
{ 
    if (iNumber==0) 
        return 1; 
    else 
        return factorial(iNumber-1);//this is what makes it recursive 
} 

[riis]

A potential danger of recursive functions is that you should be sure you don't get overflow (or maybe underflow). The factorial function is sensitive for that.
For example 13! = 6227020800, which is larger than 2 ^ 31 - 1, the maximum of an signed integer (32 bit)

Another nice one is:

int cycle(int n)
{
    if(n == 1)
        return 1;
    else if(n % 2 == 0)
        return cycle(n / 2) + 1;
    else
        return cycle(n * 3 + 1) + 1;
}

An point of interest is that there's no proof that for every positive whole number a finite number of these cycles exist. It has been proven for all numbers under one million though.
For example: if n = 22, then the number of cycles is 16.
(Note: the lowest value for n for which an int isn't large enough is 113383.)