Scribd
Upload
5 views7 pages

Recursive String Reversal Explained

The document discusses the recursive algorithm for string reversal, detailing its implementation, runtime analysis, and challenges. It highlights the base case for recursion, the algorithm steps, and includes a comparison with a factorial example to illustrate recursive function structure. The runtime analysis shows a linear growth in execution time with increasing input sizes, emphasizing the importance of understanding runtime behavior for algorithm selection.

Uploaded by

brightkorankye14
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views7 pages

Recursive String Reversal Explained

The document discusses the recursive algorithm for string reversal, detailing its implementation, runtime analysis, and challenges. It highlights the base case for recursion, the algorithm steps, and includes a comparison with a factorial example to illustrate recursive function structure. The runtime analysis shows a linear growth in execution time with increasing input sizes, emphasizing the importance of understanding runtime behavior for algorithm selection.

Uploaded by

brightkorankye14
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Recursive String

Reversal
This presentation explores the recursive algorithm for string reversal, its implementation, runtime analysis, and key
insights.

Group 14 Members
Joshua Agormeda Asare Rexford Owusu

Anthony Kwao Ayitey Bruce Emmanuel Ebo

Sylvester Kwabena Ahenkorah Bright Korankye

Amoh Paa Kobina Squire Benjamin

Boateng Appiah David Wisdom Nanayaw Umeadi

Prince Philip Adjin Tetteh


Problem Description & Recursive
Solution
Recursive string reversal involves breaking down the problem into smaller, identical subproblems. The base case is an empty or single-character string. For longer strings, the
function reverses the substring excluding the first and last characters, then swaps the first and last characters.

Algorithm Steps
Define base case (empty or single-character string).

Recursively reverse the inner part of the string.

Concatenate the last character, reversed inner part, and first character.
Python Code: Factorial
Example
While our assignment is string reversal, here's a factorial
example to illustrate recursive implementation in Python.
Key parts include the base case and the recursive call.

import timedef factorial(n): if n == 0 or n ==


1: return 1 return n * factorial(n - 1)

This snippet demonstrates the core structure of a recursive


function, handling the base case and making a call to itself
with a smaller input.
Input Sizes and
Runtimes
We measured the runtime of the recursive factorial function for various input sizes. The data shows how execution time changes as 'n' increases.

1 1 1.200

2 2 1.175

3 6 0.892

4 24 1.075

5 120 1.318

10 3628800 2.625

15 1307674368000 3.452

20 2432902008176640000 4.343
Excel Plot: Runtime vs.
Input Size
The scatter plot visualizes the relationship between input size
and runtime. A trendline, its equation, and R² value are
displayed to show the correlation.

The plot helps in understanding the practical performance of


the recursive function.
Runtime Analysis &
Complexity
The runtime increases approximately linearly with 'n', confirming the
theoretical O(n) time complexity for recursive factorial. Small
fluctuations are due to system factors.

Linear Growth
Runtime shows a nearly linear increase, aligning with O(n)
complexity.

Factorial vs.
Runtime
Factorial output grows super-exponentially, while runtime
increases modestly.

System Factors
Minor runtime fluctuations are expected due to CPU
scheduling and other system processes.
Challenges, Lessons
Learned & Conclusion
Recursive implementations are elegant but can hit stack
overflow for large inputs. Iterative methods offer safer
scalability.

Challenges Lessons Learned


Recursion depth limits for Recursive solutions are
large 'n' can lead to stack elegant for small 'n', but
overflow errors. iterative approaches are
more robust for scalability.

Conclusion
Understanding runtime behavior is crucial for choosing the
right algorithm for different problem scales.

You might also like