Unit 2 Notes

Page 1

Recursion aims to solve a large problem by solving increasingly smaller instances of the problem.

The Droste effect is an example of recursion in art.

One of the common examples of recursion used in programming is a factorial. A factorial, written as n! is every number from n to 1 multiplied together.

For a recursive solution, it helps to think of n! as n * (n-1)! instead.

We can now make a solution in pseudocode:

function factorial is: input: integer n such that n >= 1

output: [n × (n-1) × (n-2) × … × 1]

1. if n is >= 1, return [ n × factorial(n-1) ]

2. otherwise, return 1

end factorial

function factorial(ByVal n as integer)

if n >= 1 then

return n * factorial(n-1) 'recursive call

else

return 1

end if

end function

sub main()

console.writeline(factorial(10))

end sub

RECURSION