Recursion

General Intro to Recursion

What is recursion?

Recursion is a programming technique in which a function calls itself in the process of solving the problem. Recursion is good for problem-solving techniques that involve a large number of repetitive tasks, and always consist of a base case and a recursive case.

Any task that can be solved with recursion can also be solved iteratively, but the recursive case can be easier to write, simpler, more elegant, and faster than iterative solutions.

In fact, when a recursive method is actually run, the JVM will create several instances of the function on the stack. It turns out that while loops, when executed, have a similar structure, with the while loop test playing the part of the recursive base case.

Factorial Example

The factorial function in mathematics, $n!$, is defined as the product of all integers smaller than n:

$n!=n\times (n-1)\times (n-2)\times \dots \times 3\times 2\times 1$

So 3! = 3 x 2 x 1 = 6, and 5! = 5 x 4 x 3 x 2 x 1 = 120. This function can be easily expressed as a recursive function:

C:

int factorial(n) {
    if(n<=1) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

int main(void) {
    int n = 8;
    printf("Recursive factorial: %d! = %d \n", n, factorial(n) );
    return 0;
}

Perl:

sub factorial {
    my $n = $_[0];
    if($n==1) {
        return $n;
    } else {
        return $n * factorial($n - 1);
    }
}

print factorial 7;

PHP:

<?php
//  Recursive factorial function
function factorial($n) {
    if($n<1) {
        return 0;
    } else if ($n==1) {
        return 1;
    } else {
        return $n * factorial($n - 1);;
    }
}

echo factorial(7);
?>

Go:

// This is showing off how big your integer can be
// Recursive factorial
func rfactorial(n *big.Int) *big.Int {
	// See https://golang.org/pkg/math/big/

	// Initialize a bigInt with the value of 1
	one := big.NewInt(1)

	if n.Cmp(one) > 0 {
		// Recursive case
		nm1 := big.NewInt(0)
		nm1.Sub(n,one)
		return n.Mul(n, rfactorial(nm1) )
	} else {
		// Base case
		return one
	}
}

func main() {
    fmt.Println(rfactorial(big.NewInt(800)))
}

which reports back 800!:

800! = 771053011335386004144639397775028360595556401816010239163410994033970851827093069367090769795539033092647861224230677444659785152639745401480184653174909762504470638274259120173309701702610875092918816846985842150593623718603861642063078834117234098513725265045402523056575658860621238870412640219629971024686826624713383660963127048195572279707711688352620259869140994901287895747290410722496106151954257267396322405556727354786893725785838732404646243357335918597747405776328924775897564519583591354080898117023132762250714057271344110948164029940588827847780442314473200479525138318208302427727803133219305210952507605948994314345449325259594876385922128494560437296428386002940601874072732488897504223793518377180605441783116649708269946061380230531018291930510748665577803014523251797790388615033756544830374909440162270182952303329091720438210637097105616258387051884030288933650309756289188364568672104084185529365727646234588306683493594765274559497543759651733699820639731702116912963247441294200297800087061725868223880865243583365623482704395893652711840735418799773763054887588219943984673401051362280384187818611005035187862707840912942753454646054674870155072495767509778534059298038364204076299048072934501046255175378323008217670731649519955699084482330798811049166276249251326544312580289357812924825898217462848297648349400838815410152872456707653654424335818651136964880049831580548028614922852377435001511377656015730959254647171290930517340367287657007606177675483830521499707873449016844402390203746633086969747680671468541687265823637922007413849118593487710272883164905548707198762911703545119701275432473548172544699118836274377270607420652133092686282081777383674487881628800801928103015832821021286322120460874941697199487758769730544922012389694504960000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000