Recursion What is Recursion?

Factorial Expression 2:

• Factorial Expression 2:
• fact(n) = n * (n – 1) * (n – 2) * … * 1
• fact(n – 1) = (n – 1) * (n – 2) * … * 1
• fact(n – 2) = (n – 2) * … * 1
• :
• fact(1) = 1
• I.e.,
• fact(n) = n * (n – 1) * (n – 2) * … * 1
• = n * fact(n – 1)

• fact(n-1)

Solving Problems Recursively

• Suppose that the general form of the problem has some parameter n (integer)
• Simply assume that the answer for the case n-1 is known (given)
• Then express the solution for the n case in terms of the n-1 case
• Find “base case”

• This may be easy (often, fortunately) but is occasionally quite difficult
• You have to imagine that the "case n-1" solution has been handed to you for free!
• The key is to express the "case n" solution in terms of the n-1 solution
• This involves domain-specific knowledge