It’s always so exciting for a programmer when you realize a problem can be solved with a recursive function. It feels like you only had to find a solution for one simple case instead of solving it for all cases. In essence, that’s true.

A recursive function, by definition, is a function that calls itself. It calls itself again and again unless it finally finds itself in the one situation in which it know the answer to the problem.

Ideally, each recursive call makes the problem more and more likely to be solved soon. For example, let’s say you wanted to calculate the product of all the numbers 1 through 10 (10 “factorial”): 10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10

You’ll want a function that takes a number, n, and multiplies it by each number below it, down to 1. 1 is the simple case; if n=1, you return n. Otherwise, you multiple n by the factorial of n-1. As you decrease n by 1 each time the function is called, you get closer and closer to having the solution, which you achieve when you hit n=1.

function Factorial(n) { if(n==1) return n; else return n*Factorial(n-1); }

Wow, I just solved **n!** for any positive integer with a 2-line function! I don’t feel like I did any work except return n when it is 1! See what I mean about the excitement?

Sometimes, calling the function recursively doesn’t get you definitively closer to the solution, but it still gets you there. Recently, I was writing a function that generated a unique password for a user. There are two parts to it: 1) generating a random password and 2) ensuring it is unique. Turns out, a recursive function fits the bill:

function GeneratePassword() { // 1) GENERATE A RANDOM PASSWORD // In this case, passwords are a random string of numbers and letters, 8 characters long $alphanums="abcdefghijklmnopqrstuvwxyz1234567890"; $password=""; for($i=0; $i<8; $i++) { $index=rand(0,strlen($alphanums)-1); //Get position of random character $password.=substr($alphanums,$index,1); } // We have our password. // 2) IS IT UNIQUE? $sql="SELECT * FROM users WHERE password='$password'"; $result=mysql_query($sql); if(mysql_num_rows($result)>0) //NOT UNIQUE - generate a different password return GeneratePassword(); else return $password; }

Happy problem-solving!