[PYTHON] A good way to make a recursive function that reverses the characters

Concept for displaying characters in reverse order

  1. Get the last value of a particular word
  2. Delete the last value of an existing word
  3. Get the last value of the word after 2 and connect it after the obtained character of 1.
  4. Repeat steps 1 to 3 until the number of characters in the word is full.
  5. Output the acquired characters

Completion code

test.php


<?php
    function reverseStr($word,$reword){
        if(strlen($word)<1){
            return $reword;
        }
        return reverseStr(substr($word,0,-1), $reword.$word[-1]);
    }
    $word = "abcdefgh";
    echo reverseStr($word, null);
    //hgfedcba
    echo strlen("");
    //0
?>

Code description

There are various types of recursive functions, but they are created with tail recursion in mind. This will be explained while comparing the differences with ordinary recursive functions.

For tail recursion

__ Prerequisite: Input value is abcd __

test.php


<?php
    function a($word,$reword){
        if(strlen($word)<1){
            return $reword;
        }
        return a(substr($word,0,-1), $reword.$word[-1]);
    }
?>

Commentary

The transition of the function assumed when the initial input value is (abcd, "") is as follows. a(abcd,"") => a(abc,d) => a(ab,dc) => a(a,dcb) => a("",dcba) => dcba It can be said that the load on the memory is small because the values ​​are returned one by one and the processing is executed.

For normal recursion

__ Prerequisite: Input value is abcd __

test.php


<?php
   function a($word){
        if(strlen($word)<1){
            return $word;
        }
        return $word[-1] + a(substr($word,0,-1));
    }
?>

Commentary

The transition of the function assumed when the initial input value is (abcd, "") is as follows. a(abcd) => a(abcd){ d + a(abc) } => a(abcd){ d + a(abc) { c + a(ab) } } => a(abcd){ d + a(abc) { c + a(ab) { b + a(a) } } } => a(abcd){ d + a(abc) { c + a(ab) { b + a } } } => a(abcd){ d + a(abc) { c + ba } } => a(abcd){ d + cba } =>dcba

The commentary is currently being revised.

Codes in other languages ​​(for reference)

test.js


  function reverseStr(word, reword){
      if(word.length < 1){
          return reword;
      }
      return reverseStr(word.slice(0,-1), reword + word.slice(-1));
  }
  var word = "abcdefgh";
  console.log(reverseStr(word, ""));

test.rb


def reverseStr(word, reword)
   if(word.length < 1)
       return reword
   end
   return reverseStr(word[0..-2],reword+word[-1])
end
word = "abcdefgh"
puts reverseStr(word, "")

test.py


def reveseStr(word, reword):
    if len(word) < 1:
        return reword
    return reveseStr(word[0:-1], reword + word[-1])
    
word = "abcdefgh"
print(reveseStr(word, ""))

Recommended Posts

A good way to make a recursive function that reverses the characters
How to identify the path that is easy to make a mistake
Introduction to Recursive Functions: What is a Recursive Function?
Make a margin to the left of the TextField
How to make a follow function in Rails
[Ruby] I want to make a program that displays today's day of the week!
I tried to make a login function in Java
How to make a mod for Slay the Spire
I want to add a delete function to the comment function
[Java] I tried to make a rock-paper-scissors game that beginners can run on the console.
[Docker] Is it good enough to call it a multi-stage build? → The story that became so good
I want to make a function with kotlin and java!
[Rails] A simple way to implement a self-introduction function in your profile
How to create a registration / update function where the table crosses
Easy way to create a mapping class when using the API
[Rails] How to put a crown mark on the ranking function
[Java] I tried to make a maze by the digging method ♪
Try to make a CS 3D tile from the Geographical Survey tile
[Illustration] Finding the sum of coins with a recursive function [Ruby]
Let's make a custom_cop that points out the shaking of the name
(Ruby on Rails6) Create a function to edit the posted content
I tried to make a group function (bulletin board) with Rails
How to make a Java container
How to make a JDBC driver
How to make a splash screen
How to make a Jenkins plugin
How to add the delete function
Try to make a peepable iterator
How to make a Java array
A memo that was soberly addicted to the request of multipart / form-data
How to interact with a server that does not crash the app
A program that determines whether the entered integer is close to an integer
I tried to make a Web API that connects to DB with Quarkus
JVM Performance Tuning: What is Tuning and How to Make a Good Plan
I thought about the best way to create a ValueObject in Ruby
A story that was embarrassing to give anison file to the production environment
[Ruby] Returns characters in a pyramid shape according to the entered numbers
[Java] Implement a function that uses a class implemented in the Builder pattern
I tried to make a program that searches for the target class from the process that is overloaded with Java