CS 121 Lecture Notes - Lecture 75: Infinite Loop
• Recursion:
➢ A programming technique in which a method calls itself in order to fulfill its
purpose.
➢ Process of defining something in terms of itself.
➢ A list can be defined recursively:
a List is a: number
or a: number comma List
➢ No matter how long a list is, recursive definition describes it.
o A list of 1 element is defined completely by the first (non-recursive) part
of the definition.
o For any list longer than 1 element, recursive part of the definition (the
part which refers to itself) is used as many times as necessary until last
element is reached.
o The last element in the list is always defined by non-recursive part of the
definition.
• Infinite Recursion:
➢ Definition of List contains one option that’s recursive & one option that’s.
➢ The part of the definition that is not recursive is called the base case.
➢ If all options had a recursive component, recursion would never end.
o EX: If definition of List was simply a number followed by a comma
followed by a List , no list could ever end.
▪ This problem is called infinite recursion.
▪ It is similar to an infinite loop except the loop occurs in the
definition itself.
❖ A programmer must be careful to design algorithms so they avoid
infinite recursion.
find more resources at oneclass.com
find more resources at oneclass.com