cs 320 lecture 03 Tail-Recursion-Prolog

CS320: Tail Recursion and Complexity

Instructor

• Darrell Whitley

Jeopardy Game Components

• Game Name: Let's Play Jeopardy!

• Points: $3,400 for each question

• Other Elements: MAOMIS, सोचिए

Building WATSON by IBM

• Objective: Develop WATSON using all available data, specifically Wikipedia, as a Knowledge Base.

• Process:

  • Utilize Natural Language Processing (NLP) to convert English to Prolog.

  • Query the knowledge base in a structured format.

IBM Publications Related to WATSON

• Title: Natural Language Processing With Prolog in the IBM Watson System

  • Authors: Adam Lally (IBM), Paul Fodor (Stony Brook University)

  • Context: Discusses application of Prolog in enhancing IBM Watson’s capabilities

  • Publication Date: March 31, 2011

Prolog Overview

• Prolog Characteristics:

  • Type: Declarative and non-procedural language.

  • Functionality: Programmer defines the goals, not the methods to achieve them.

Prolog Member Function

• Definition:

  • member(X, [X|Y]). indicates X is the first element.

  • member(X, [Head|Tail]) :- member(X, Tail). checks if X is in the Tail of the list.

• Usage Example:

  • To check membership: ? member(1, [3, 2, 4, 1, 5]). returns the result by recursively tracing through the list.

Tail Recursion in Prolog

• Tail Recursive Member Function:

  • Efficient in terms of stack space as it allows the stack to be reused.

• Example:

  • member(1, [3, 2, 4, 1, 5]). follows similar replacement logic to demonstrate tail recursion.

Complexity Analysis

• Characteristic Equation:

  • Defined as: F(N) = F(N-1)

  • Base case: F(1) = C = O(1)

• Complexity:

  • The member function has O(n) complexity in the average case.

Factorial Functions in Prolog

• Non-Tail Recursive Factorial:

  • ffactorial(1, 1).

• Tail Recursive Factorial:

  • fantail(1, Temp, Temp) :- !.

  • Demonstrates accumulation with Temp variable.

Comparison with Python

• Standard Recursion:

  def factorial(n):
      if n == 0:
          return 1
      else:
          return n * factorial(n - 1)

• Tail Recursion:

  def factorial(n, acc=1):
      if n == 0:
          return acc
      else:
          return factorial(n - 1, acc * n)

Limitations of Tail Recursion in Python

• Note: Python does not support Tail Call Optimization (TCO).

• Other Languages: TCO is also unsupported in Java, C#, or Ruby.

• Supported Languages: Scheme and Haskell support TCO.