CSCI 3137 - Recursion in Scheme

Parabola Function

• Parabola is defined by the quadratic function: ( y = ax^2 + bx + c ).
• Scheme function structure: ( (define parabola (lambda (x)...)) ) needs completion.

Functional Programming and Recursion

• Iterations often involve mutable variables, leading to side effects, which are undesirable in functional programming.
• Recursion can replace loops, maintaining immutability.

Recursion Fundamentals

• Establish a function with base cases to terminate and recursive cases to move closer to base.
• Recursive functions call themselves with modified parameters to progress toward base case.

Factorial Function

• Factorial defined as:
  • ( n! = 1 ) if ( n == 0 )
  • ( n! = n \times (n-1)! ) if ( n > 0 ).
• Needs completion for the Scheme definition: ( (define factorial (lambda (n)...)) ).

Stack Overflow and Recursion

• Evaluating ( (factorial 1000) ) causes StackOverflowError due to recursion depth.
• Each recursive call produces a unique stack frame, consuming stack space.

Tail Recursion

• Recursive calls that perform their last action as another recursive call are called tail-recursive.
• Tail recursion allows stack frames to be reused, simulating loops in recursion.

Improving the Factorial Function

• The traditional factorial function lacks tail recursion.
• Proposed solution involves a helper function to implement tail recursion.
• Example structure:
  • ( (define fact-helper (lambda (n m fm)...)) )
  • ( (define factorial (lambda (n) (if (< n 0) 1 (fact-helper n 1 1)))) ).

Local Binding with let

• let allows variable bindings for expressions, isolating names within the expression context.
• Variables must remain independent.

Fibonacci Function with let

• Structure for Fibonacci can be completed using let:
  • ( (define fibonacci (lambda (n) (if (< n 2) n (let ((fn-1...) (fn-2...))...)))) ).

Named let

• Named let allows recursive evaluations without cluttering the variable namespace.
• Format:
  • ( (let name ((name1 expr1) (name2 expr2)...) expression) )
• Inside the expression, name can refer to the recursive call.

Final Fibonacci Implementation

• An optimized Fibonacci function using named let:
  • If ( n < 2 ), return ( n ); otherwise, define f to compute based on the recurrence relation.

Exercise on Factorial with Named let

• A different approach using named let for factorial is suggested.

Padovan Sequence

• Defined by:
  • ( P(0) = P(1) = P(2) = 1 )
  • Recurrence relation: ( P(n) = P(n-2) + P(n-3) ).
• Complete the definition: ( (define padovan (lambda (n)...)) ).

This quiz covers the concepts of recursion and functional programming in Scheme, particularly focusing on defining parabolic functions. You will work on completing a function definition and understand the challenges of iterative structures in functional programming.