Recursion What is Recursion?

Recursion

What is Recursion?

• Originally, the concept from math:
• To calculate something by repeatedly applying some operation
• One classical example is the equation for n factorial, represented n!. Let us consider its expression 1 and 2. They lead to two different computing techniques, iterative and recursive.
• So, recursion is a technique for expressing the solution to a problem in terms of smaller problems of the same type
• It is a conceptually very elegant approach
• It has great expressive power: recursive code is usually very compact
• It will be used in this subject frequently

Factorial Expression 1:

• Factorial Expression 1:
• fact(n) = n * (n – 1) * (n – 2) * … * 1
• = n * (n – 1) * … * (n – (n –1))
• public int fact ( int n )
• {
• int f = 1;
• for ( int i = 1; i <= n; i++)
• f = f * i;
• // loop invariant: f = fact(i)
• return f;
• }

• An awkward definition