Chapter 19.2: Recursion

9618 AS/A Level Computer Science - Python Programming

📚 Learning Objectives

Understand the concept of recursion and how it works
Identify the three key features of a recursive algorithm
Write and trace recursive functions in Python and Pseudocode
Understand the difference between base case and general case
Explain the winding and unwinding phases of recursion
Understand the call stack and stack frames
Translate between recursive and iterative solutions
Compare benefits and drawbacks of recursion vs iteration

📖 Prior Knowledge Required

Understanding of functions and procedures
Knowledge of parameters and return values
Basic understanding of iteration (loops)
Familiarity with conditional statements (IF/ELSE)
Understanding of local variables and scope

💡 Important Note

For this chapter, all examples will be shown in both CIE Pseudocode and Python to help you understand the concepts in both formats used in exams.

1. What is Recursion?

Recursion is a highly effective programming technique where a function calls itself to solve a problem or execute a task. Unlike iterative loops, recursion doesn't rely on loop constructs. Instead, it uses the idea of self-reference to break down complicated problems into more manageable subproblems.

📖 Definition

Recursion is a process using a function or procedure that is defined in terms of itself and calls itself. The process is defined using a base case (a terminating solution that is not recursive) and a general case (a solution that is recursively defined).

1.1 Three Key Features of Recursion

⚠️ Three Essential Features

A recursive algorithm must have these three features:

The function/procedure must call itself
A base case - a condition that returns a value without further recursive calls
A stopping condition - must be reachable after a finite number of calls

💡 Exam Tip

Remember: Every recursive function MUST have a base case! Without it, the function would call itself indefinitely, causing a stack overflow error.

2. Example 1: Factorial Function

Let's look at a classic example: calculating the factorial of a number. The factorial of n (written as n!) is the product of all positive integers from 1 to n.

n! = n × (n-1)! where 0! = 1 and 1! = 1

2.1 Factorial in Pseudocode

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER // Base case: factorial of 0 or 1 is 1 IF n = 0 OR n = 1 THEN RETURN 1 ELSE // Recursive case: n! = n * (n-1)! RETURN n * Factorial(n - 1) ENDIF ENDFUNCTION

2.2 Factorial in Python

def factorial(n):
    # Base case: factorial of 0 or 1 is 1
    if n == 0 or n == 1:
        return 1
    else:
        # Recursive case: n! = n * (n-1)!
        return n * factorial(n - 1)

# Example usage
result = factorial(5)
print(result)  # Output: 120

📖 How Factorial(5) Works

factorial(5) → returns 5 × factorial(4)
factorial(4) → returns 4 × factorial(3)
factorial(3) → returns 3 × factorial(2)
factorial(2) → returns 2 × factorial(1)
factorial(1) → returns 1 (base case reached!)
Unwinding: 2×1=2, 3×2=6, 4×6=24, 5×24=120

3. Tracing Factorial(3) - Winding & Unwinding

Let's trace Factorial(3) step by step to understand the winding and unwinding process.

Phase	Call	Action	Stack
WINDING	Factorial(3)	3 ≠ 0,1 → calls Factorial(2)	[Factorial(3)]
	Factorial(2)	2 ≠ 0,1 → calls Factorial(1)	[Factorial(3), Factorial(2)]
	Factorial(1)	1 = 1 → returns 1 (BASE)	[Factorial(3), Factorial(2), Factorial(1)]
UNWINDING	Factorial(1)	returns 1	[Factorial(3), Factorial(2)]
	Factorial(2)	returns 2 × 1 = 2	[Factorial(3)]
	Factorial(3)	returns 3 × 2 = 6	[]

📝 Trace Table for Factorial(3)

Call	n	Condition	Return Value
1	3	3 ≠ 0,1	3 × Factorial(2)
2	2	2 ≠ 0,1	2 × Factorial(1)
3	1	1 = 1 ✓	1 (BASE CASE)
2	2	—	2 × 1 = 2
1	3	—	3 × 2 = 6

🧠 Memory Trick: The Ladder

Think of recursion like climbing a ladder:

WINDING = Climbing UP (each rung = a function call on stack)
BASE CASE = Top of ladder (stop climbing, start descending)
UNWINDING = Climbing DOWN (returning values as you descend)

4. Example 2: Countdown Function

A simple countdown program that prints numbers from n down to 0.

4.1 Countdown in Pseudocode

PROCEDURE Countdown(n : INTEGER) // Output current value OUTPUT n // Base case: stop when n reaches 0 IF n = 0 THEN RETURN ENDIF // Recursive call with decremented value Countdown(n - 1) ENDPROCEDURE // Call the procedure Countdown(5)

4.2 Countdown in Python

def countdown(n):
    # Output current value
    print(n)
    
    # Base case: stop when n reaches 0
    if n == 0:
        return
    
    # Recursive call with decremented value
    countdown(n - 1)

# Call the function
countdown(5)

Output: 5, 4, 3, 2, 1, 0

💡 Key Point

Notice the order: we print FIRST, then make the recursive call. This means each value is printed during the winding phase. If we printed after the recursive call, values would print during unwinding (in reverse: 0, 1, 2, 3, 4, 5).

5. Example 3: Sum Function

Calculate the sum of all integers from 1 to n.

Sum(n) = n + Sum(n-1) where Sum(1) = 1

5.1 Sum in Pseudocode

FUNCTION Sum(n : INTEGER) RETURNS INTEGER // Base case IF n = 1 THEN RETURN 1 ENDIF // Recursive case RETURN n + Sum(n - 1) ENDFUNCTION

5.2 Sum in Python

def sum_to_n(n):
    # Base case
    if n == 1:
        return 1
    
    # Recursive case
    return n + sum_to_n(n - 1)

# Example usage
result = sum_to_n(5)
print(result)  # Output: 15 (1+2+3+4+5)

📖 How Sum(5) Works

Sum(5) = 5 + Sum(4) = 5 + 4 + Sum(3) = 5 + 4 + 3 + Sum(2) = 5 + 4 + 3 + 2 + Sum(1) = 5 + 4 + 3 + 2 + 1 = 15

6. Example 4: Power Function

Calculate x raised to the power n (x^n) using recursion.

x^n = x × x^(n-1) where x^0 = 1

6.1 Power in Pseudocode

FUNCTION Power(x, n : INTEGER) RETURNS INTEGER // Base case: any number to power 0 is 1 IF n = 0 THEN RETURN 1 ENDIF // Recursive case RETURN x * Power(x, n - 1) ENDFUNCTION

6.2 Power in Python

def power(x, n):
    # Base case: any number to power 0 is 1
    if n == 0:
        return 1
    
    # Recursive case
    return x * power(x, n - 1)

# Example usage
result = power(2, 5)
print(result)  # Output: 32 (2^5 = 32)

Trace for Power(2, 3):
Power(2, 3) → 2 × Power(2, 2) → 2 × 2 × Power(2, 1) → 2 × 2 × 2 × Power(2, 0) → 2 × 2 × 2 × 1 = 8

7. Example 5: Fibonacci Sequence

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21... Each number is the sum of the two preceding ones.

Fib(n) = Fib(n-1) + Fib(n-2) where Fib(0) = 0, Fib(1) = 1

7.1 Fibonacci in Pseudocode

FUNCTION Fibonacci(n : INTEGER) RETURNS INTEGER // Base cases IF n = 0 THEN RETURN 0 ENDIF IF n = 1 THEN RETURN 1 ENDIF // Recursive case RETURN Fibonacci(n - 1) + Fibonacci(n - 2) ENDFUNCTION

7.2 Fibonacci in Python

def fibonacci(n):
    # Base cases
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    # Recursive case
    return fibonacci(n - 1) + fibonacci(n - 2)

# Example usage
result = fibonacci(6)
print(result)  # Output: 8 (0,1,1,2,3,5,8)

⚠️ Important Warning

This naive Fibonacci implementation has TWO recursive calls, making it very inefficient (exponential time complexity O(2^n)). For large n, this can cause severe performance issues. The iterative approach is much more efficient.

8. Recursion vs Iteration

The same problem can often be solved using either recursion or iteration. Let's compare both approaches.

8.1 Side-by-Side Comparison: Countdown

📝 Pseudocode - Recursive
PROCEDURE Countdown(n)
    OUTPUT n
    IF n = 0
    THEN
        RETURN
    ENDIF
    Countdown(n - 1)
ENDPROCEDURE

📝 Pseudocode - Iterative
PROCEDURE Countdown(n)
    WHILE n >= 0 DO
        OUTPUT n
        n ← n - 1
    ENDWHILE
ENDPROCEDURE

🐍 Python - Recursive
def countdown_rec(n):
    print(n)
    if n == 0:
        return
    countdown_rec(n - 1)

🐍 Python - Iterative
def countdown_iter(n):
    while n >= 0:
        print(n)
        n = n - 1

8.2 Benefits and Drawbacks

	Recursion	Iteration
Benefits	• More concise code • Elegant for complex problems • Natural for trees/fractals • Easier to read (sometimes)	• More efficient (less memory) • Faster execution • Easier to debug • No stack overflow risk
Drawbacks	• Higher memory usage • Slower (function call overhead) • Harder to debug • Stack overflow risk	• Can require more code • Less elegant for some problems • More complex for trees/fractals

💡 Exam Tip

In exams, always mention that iteration uses less memory because it doesn't build up a call stack. Recursion uses more memory because each call adds a frame to the stack.

9. The Call Stack

When a recursive function is called, the compiler/interpreter uses a call stack to keep track of each function call. Each call creates a stack frame containing important information.

📖 Stack Frame Contents

Each stack frame contains:

The function name
The parameter values for that call
The local variables (and their values)
The return address (where to resume after returning)

10. Stack Overflow

⚠️ Critical Warning

If no base case is present, or if the base case is never reached, the stack never stops growing. This leads to a stack overflow, causing the program to crash.

10.1 Example of Infinite Recursion

📝 Pseudocode - WRONG!
FUNCTION BadRecursion(n)
    // No base case!
    RETURN n * BadRecursion(n - 1)
ENDFUNCTION

🐍 Python - WRONG!
def bad_recursion(n):
    # No base case!
    return n * bad_recursion(n - 1)

❌ This Will Crash!

Without a base case, this function will call itself infinitely. Each call adds a frame to the stack until memory is exhausted → Stack Overflow Error!

📖 How Compilers Implement Recursion

To implement recursive procedures and functions, a compiler must produce object code that:

Pushes return addresses and local variable values onto the stack (winding)
Pops return addresses and local variable values off the stack (unwinding)

Example: factorial(100) would require 100 stack frames to be created before unwinding begins. For very large inputs, even correct recursion can cause stack overflow!

11. Example 6: Reverse a String

Recursively reverse a string by taking the last character and concatenating it with the reverse of the remaining string.

11.1 Reverse in Pseudocode

FUNCTION Reverse(s : STRING) RETURNS STRING // Base case: empty string or single character IF LENGTH(s) <= 1 THEN RETURN s ENDIF // Recursive case: last char + reverse of rest RETURN SUBSTRING(s, LENGTH(s), 1) + Reverse(SUBSTRING(s, 1, LENGTH(s) - 1)) ENDFUNCTION

11.2 Reverse in Python

def reverse_string(s):
    # Base case: empty string or single character
    if len(s) <= 1:
        return s
    
    # Recursive case: last char + reverse of rest
    return s[-1] + reverse_string(s[:-1])

# Example usage
result = reverse_string("HELLO")
print(result)  # Output: OLLEH

📖 How It Works

reverse_string("HELLO"):

"O" + reverse("HELL")
"O" + "L" + reverse("HEL")
"O" + "L" + "L" + reverse("HE")
"O" + "L" + "L" + "E" + reverse("H")
"O" + "L" + "L" + "E" + "H" (base case)
Result: "OLLEH"

12. Key Concepts Summary

Concept	Description
Recursion	A function/procedure that calls itself
Base Case	Stopping condition; returns without further recursion
General Case	Recursive part that calls itself with modified parameters
Winding	Phase where calls build up on the stack
Unwinding	Phase where calls return values from base case
Call Stack	Structure storing active function calls
Stack Frame	Single call snapshot (params, locals, return address)
Stack Overflow	Error from infinite recursion exhausting memory

🌟 Examples Covered

Example	Base Case	Recursive Case
Factorial(n)	n = 0 or 1 → return 1	return n × factorial(n-1)
Countdown(n)	n = 0 → return	countdown(n-1)
Sum(n)	n = 1 → return 1	return n + sum(n-1)
Power(x, n)	n = 0 → return 1	return x × power(x, n-1)
Fibonacci(n)	n = 0 → 0, n = 1 → 1	fib(n-1) + fib(n-2)
Reverse(s)	length ≤ 1 → return s	last_char + reverse(rest)

13. Exam-Style Questions

1. Define what is meant by "recursion" in programming. Explain the difference between a base case and a general case. [4 marks]

Answer:

Recursion is a programming technique where a function or procedure calls itself to solve a problem by breaking it into smaller subproblems.

Base Case:

A terminating condition that stops the recursion
Returns a value without making further recursive calls
Example: In factorial, base case is n = 0 or n = 1

General Case:

The recursive part of the function
Calls itself with modified parameters moving toward base case
Example: In factorial, general case is return n × factorial(n-1)

2. Write a recursive function in pseudocode to calculate the sum of all even numbers from 2 to n (assume n is even). [5 marks]

Answer (Pseudocode):

FUNCTION SumEven(n : INTEGER) RETURNS INTEGER // Base case IF n = 2 THEN RETURN 2 ENDIF // Recursive case RETURN n + SumEven(n - 2) ENDFUNCTION

Answer (Python):

def sum_even(n):
    if n == 2:
        return 2
    return n + sum_even(n - 2)

Example: SumEven(6) = 6 + SumEven(4) = 6 + 4 + SumEven(2) = 6 + 4 + 2 = 12

3. Trace the execution of Factorial(4). Show the call stack at its deepest point and explain the unwinding process. [6 marks]

Winding Phase (Stack grows):

Call 1: Factorial(4) → n=4, n≠0,1 → calls Factorial(3)
Call 2: Factorial(3) → n=3, n≠0,1 → calls Factorial(2)
Call 3: Factorial(2) → n=2, n≠0,1 → calls Factorial(1)
Call 4: Factorial(1) → n=1, n=1 → BASE CASE! Returns 1

Call Stack at Deepest Point:

[Factorial(4)] ← Bottom
[Factorial(3)]
[Factorial(2)]
[Factorial(1)] ← Top (BASE CASE)

Unwinding Phase:

Factorial(1) returns 1
Factorial(2) returns 2 × 1 = 2
Factorial(3) returns 3 × 2 = 6
Factorial(4) returns 4 × 6 = 24

Final Result: 24

4. Convert this recursive pseudocode to an iterative version. Explain one advantage of the iterative approach. [5 marks]

Recursive Version (Given):

FUNCTION Countdown(n : INTEGER) OUTPUT n IF n = 0 THEN RETURN ENDIF Countdown(n - 1) ENDFUNCTION

Iterative Version (Pseudocode):

PROCEDURE Countdown(n : INTEGER) WHILE n >= 0 DO OUTPUT n n ← n - 1 ENDWHILE ENDPROCEDURE

Advantage: The iterative approach uses less memory because it doesn't build up a call stack. It's also faster due to no function call overhead and easier to debug since the flow is linear.

5. Explain why the following recursive function will cause a stack overflow. Rewrite it correctly in both pseudocode and Python.
def bad_factorial(n): return n * bad_factorial(n-1) [6 marks]

Why it causes stack overflow:

The function has no base case
It will call itself indefinitely
Each call adds a frame to the stack without ever removing any
Eventually the stack memory is exhausted

Corrected Pseudocode:

FUNCTION Factorial(n : INTEGER) RETURNS INTEGER IF n = 0 OR n = 1 THEN RETURN 1 ENDIF RETURN n * Factorial(n - 1) ENDFUNCTION

Corrected Python:

def factorial(n):
    if n == 0 or n == 1:  # Base case added!
        return 1
    return n * factorial(n - 1)

6. Write a recursive function in both pseudocode and Python to check if a string is a palindrome (reads the same forwards and backwards). [6 marks]

Pseudocode:

FUNCTION IsPalindrome(s : STRING) RETURNS BOOLEAN // Base case: empty or single character IF LENGTH(s) <= 1 THEN RETURN TRUE ENDIF // Check first and last characters IF SUBSTRING(s, 1, 1) ≠ SUBSTRING(s, LENGTH(s), 1) THEN RETURN FALSE ENDIF // Recursive case: check middle portion RETURN IsPalindrome(SUBSTRING(s, 2, LENGTH(s) - 2)) ENDFUNCTION

Python:

def is_palindrome(s):
    # Base case: empty or single character
    if len(s) <= 1:
        return True
    
    # Check first and last characters
    if s[0] != s[-1]:
        return False
    
    # Recursive case: check middle portion
    return is_palindrome(s[1:-1])

7. Compare three differences between recursion and iteration. Include memory usage in your answer. [6 marks]

Aspect	Recursion	Iteration
Memory	Higher usage - each call adds a stack frame	Lower usage - no call stack buildup
Speed	Slower - function call overhead	Faster - direct loop execution
Debugging	Harder - multiple stack frames to trace	Easier - linear flow, single context
Code Size	Often more concise	Can require more lines
Use Cases	Trees, fractals, divide-and-conquer	Simple repetition, linear tasks

8. What is stored in a stack frame? Explain why understanding stack frames is important for debugging recursive functions. [5 marks]

Stack Frame Contents:

Function name - identifies which function is executing
Parameter values - the arguments passed to this call
Local variables - variables declared within the function
Return address - where to resume after this call returns
Space for return value - where the result will be stored

Why it's important for debugging:

Helps trace the sequence of calls
Shows parameter values at each level
Identifies where infinite recursion might occur
Helps understand winding vs unwinding phases

13. Exam-Style Questions (Continued)

9. Write a recursive function to calculate x^n (x raised to power n) in both pseudocode and Python. Then trace Power(2, 4). [8 marks]

Pseudocode:

FUNCTION Power(x, n : INTEGER) RETURNS INTEGER IF n = 0 THEN RETURN 1 ENDIF RETURN x * Power(x, n - 1) ENDFUNCTION

Python:

def power(x, n):
    if n == 0:
        return 1
    return x * power(x, n - 1)

Trace for Power(2, 4):

Call	x	n	Action	Return
1	2	4	n ≠ 0	2 × Power(2,3)
2	2	3	n ≠ 0	2 × Power(2,2)
3	2	2	n ≠ 0	2 × Power(2,1)
4	2	1	n ≠ 0	2 × Power(2,0)
5	2	0	n = 0 ✓	1 (BASE)
4	2	1	Unwind	2 × 1 = 2
3	2	2	Unwind	2 × 2 = 4
2	2	3	Unwind	2 × 4 = 8
1	2	4	Unwind	2 × 8 = 16

10. Explain the terms "winding" and "unwinding" in the context of recursion. Give an example using factorial(3). [6 marks]

Winding:

The phase where function calls build up on the stack
Each call is pushed onto the call stack
Statements after the recursive call are NOT executed
Continues until the base case is reached

Unwinding:

The phase where function calls return values
Stack frames are popped off the call stack
Values are passed back up through the chain
Starts from the base case and works back to original call

Example - factorial(3):

WINDING:
  factorial(3) called → stack: [factorial(3)]
  factorial(2) called → stack: [factorial(3), factorial(2)]
  factorial(1) called → stack: [factorial(3), factorial(2), factorial(1)]
  BASE CASE reached!

UNWINDING:
  factorial(1) returns 1 → stack: [factorial(3), factorial(2)]
  factorial(2) returns 2×1=2 → stack: [factorial(3)]
  factorial(3) returns 3×2=6 → stack: []

11. A programmer writes a recursive function to calculate the nth Fibonacci number. Explain why this might be inefficient for large values of n. [4 marks]

Answer:

The naive recursive Fibonacci makes TWO recursive calls for each non-base case
This creates a binary tree of calls, leading to exponential time complexity O(2^n)
Many values are recalculated multiple times (e.g., fib(3) is calculated multiple times when finding fib(6))
For large n, the number of function calls becomes astronomically large
Can cause severe performance issues and potential stack overflow

Better approaches: Use iteration, or memoization to store previously calculated values.

12. Write a recursive procedure in pseudocode that prints all numbers from n down to 1, then prints "Done!". [5 marks]

Pseudocode:

PROCEDURE CountAndDone(n : INTEGER) // Output current number OUTPUT n // Base case IF n = 1 THEN OUTPUT "Done!" RETURN ENDIF // Recursive call CountAndDone(n - 1) ENDPROCEDURE

Python:

def count_and_done(n):
    print(n)
    if n == 1:
        print("Done!")
        return
    count_and_done(n - 1)

Example Output for CountAndDone(5): 5, 4, 3, 2, 1, Done!

14. Glossary

📖 Key Terms

Recursion → A programming technique where a function or procedure calls itself to solve a problem by breaking it into smaller subproblems.

Base Case → A terminating condition in a recursive function that returns a value without making further recursive calls. Essential to prevent infinite recursion.

General Case → The recursive part of a function that calls itself with modified parameters, typically operating on a smaller instance of the problem.

Stopping Condition → A condition that must be reachable after a finite number of recursive calls; ensures the recursion terminates properly.

Winding → The phase of recursion where function calls are being added to the call stack. Statements after the recursive call are not executed during this phase.

Unwinding → The phase of recursion where function calls return values, starting from the base case and working back up through the call stack.

Call Stack → A data structure used by the compiler/interpreter to keep track of active function calls. Stores return addresses, parameters, and local variables.

Stack Frame → A single entry on the call stack containing information about one function call: function name, parameters, local variables, and return address.

Stack Overflow → An error that occurs when the call stack exceeds its allocated memory, typically caused by infinite or very deep recursion without a proper base case.

Iteration → A programming technique using loops (FOR, WHILE, REPEAT) to repeat a block of code. An alternative approach to recursion.

Divide and Conquer → A problem-solving strategy where a problem is broken into smaller subproblems, solved independently, and combined. Often implemented using recursion.

Self-Reference → The concept of a function, procedure, or definition referring to itself within its own definition.

15. Exam Success Tips

💡 Tip 1: Always Identify the Base Case First

Before writing any recursive function, ask: "What is the simplest case where I know the answer?" This is your base case. For factorial, it's n=0 or n=1. For countdown, it's n=0.

💡 Tip 2: Understand Winding vs Unwinding

WINDING: Calls build up → No return values yet → Statements AFTER recursive call NOT executed

UNWINDING: Calls return values → Stack shrinks → Statements AFTER recursive call ARE executed

🧠 Memory Trick: The Ladder Analogy

WINDING = Climbing UP a ladder (each rung = a function call)
BASE CASE = Top of the ladder (stop climbing!)
UNWINDING = Climbing DOWN (returning values as you descend)
You can't come down until you reach the top!

❌ Common Mistakes to Avoid

Forgetting the base case - Most common error! Always check for this.
Base case never reached - Ensure each call moves toward the base case.
Wrong parameter modification - Make sure parameter changes correctly (n-1, not n).
Confusing winding/unwinding - Remember: statements after call execute during unwinding.
Stack overflow misconception - It's about memory exhaustion, not speed.

💡 Tip 3: Tracing in Exams

When asked to trace a recursive function:

Create a trace table with columns for function call, parameters, and return values
Draw the call stack visually if needed
Show each stack frame with its local values
Mark where base case is reached
Show the unwinding process with computed values

16. Key Takeaways

📌 Summary Points

Core Concepts

Recursion = Function calls itself to solve smaller instances of a problem
Base Case = Stopping condition; returns without further recursion (ESSENTIAL!)
General Case = Recursive call with modified parameters moving toward base case

Execution Process

Winding = Calls build up on stack; statements after recursive call NOT executed
Unwinding = Returns values from base case back up; stack frames removed
Call Stack = Stores function calls, parameters, local variables, return addresses

Recursion vs Iteration

Recursion: More concise, elegant for complex problems, higher memory usage
Iteration: More efficient, easier to debug, lower memory usage
Both can solve the same problems; choose based on requirements

Critical Warnings

Never forget the base case - causes stack overflow
Ensure base case is reachable - finite steps to termination
Deep recursion can exhaust stack memory even with correct base case

🌟 Quick Reference: All Examples

Function	Base Case	Recursive Case
Factorial(n)	n ≤ 1 → return 1	n × factorial(n-1)
Countdown(n)	n = 0 → return	countdown(n-1)
Sum(n)	n = 1 → return 1	n + sum(n-1)
Power(x, n)	n = 0 → return 1	x × power(x, n-1)
Fibonacci(n)	n ≤ 1 → return n	fib(n-1) + fib(n-2)
Reverse(s)	len ≤ 1 → return s	last + reverse(rest)
IsPalindrome(s)	len ≤ 1 → TRUE	first=last AND middle