Recursion is Natural

“Yay! I can see my bu** !! … wait, it’s not my bu**, it’s myself !”

If you can come to the last realization that you are seeing yourself then you already understand recursion is natural. If not, the following few examples may help.

Example 1: Is Even?

Zero is even. Any integer N > 0 is even if N-1 is not even.

Example 2: Factorial

Factorial of zero is 1. Factorial of any integer N > 0 is N times factorial of N-1.

Example 2: Length of a List

An empty list has a length zero. Any other list has one head element and a sub list called the tail. So length is 1 more than the length of the tail.

Example 3: Map f() to List S

If S is empty then nothing to do just return an empty list. If not map f() to the tail and get a mapped list. Then add f(head) to the front of that list.

P.S. Many thanks to Dan Friedman (https://www.cs.indiana.edu/~dfried/) for his great class of B521 (cs.indiana.edu/classes/b521) at IU, 2009.

----------

About the image; it’s an InkScape sketching of the image I found at http://contortionistsunite.ning.com/profiles/blogs/day-1-3