diff --git a/gdb/infrun.c b/gdb/infrun.c
index 4fde96800fb..9571acef1fa 100644
--- a/gdb/infrun.c
+++ b/gdb/infrun.c
@@ -6925,6 +6925,11 @@ process_event_stop_test (struct execution_control_state *ecs)
   frame = get_current_frame ();
   gdbarch = get_frame_arch (frame);
 
+  /* Shorthand to make if statements smaller.  */
+  struct frame_id original_frame_id
+    = ecs->event_thread->control.step_frame_id;
+  struct frame_id curr_frame_id = get_frame_id (get_current_frame ());
+
   switch (what.main_action)
     {
     case BPSTAT_WHAT_SET_LONGJMP_RESUME:
@@ -7724,6 +7729,19 @@ process_event_stop_test (struct execution_control_state *ecs)
 			       "it's not the start of a statement");
 	}
     }
+  else if (execution_direction == EXEC_REVERSE
+	  && curr_frame_id != original_frame_id
+	  && original_frame_id.code_addr_p && curr_frame_id.code_addr_p
+	  && original_frame_id.code_addr == curr_frame_id.code_addr)
+    {
+      /* If we enter here, we're leaving a recursive function call.  In this
+	 situation, we shouldn't refresh the step information, because if we
+	 do, we'll lose the frame_id of when we started stepping, and this
+	 will make GDB not know we need to print frame information.  */
+      refresh_step_info = false;
+      infrun_debug_printf ("reverse stepping, left a recursive call, don't "
+			   "update step info so we remember we left a frame");
+    }
 
   /* We aren't done stepping.
 
diff --git a/gdb/testsuite/gdb.dwarf2/dw2-out-of-range-end-of-seq.exp b/gdb/testsuite/gdb.dwarf2/dw2-out-of-range-end-of-seq.exp
index d2c28a87923..8b4e79644c1 100644
--- a/gdb/testsuite/gdb.dwarf2/dw2-out-of-range-end-of-seq.exp
+++ b/gdb/testsuite/gdb.dwarf2/dw2-out-of-range-end-of-seq.exp
@@ -84,7 +84,7 @@ if ![runto_main] {
 }
 
 set test "END with address 1 eliminated"
-gdb_test_multiple "maint info line-table $srcfile$" $test {
+gdb_test_multiple "maint info line-table \\b$srcfile$" $test {
     -re -wrap "END *0x0*1 *$hex *Y *\r\n.*" {
 	fail $gdb_test_name
     }
diff --git a/gdb/testsuite/gdb.reverse/recursion.c b/gdb/testsuite/gdb.reverse/recursion.c
new file mode 100644
index 00000000000..5ce1c8dbea0
--- /dev/null
+++ b/gdb/testsuite/gdb.reverse/recursion.c
@@ -0,0 +1,44 @@
+/* This testcase is part of GDB, the GNU debugger.
+
+   Copyright 2023 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+/* Test GDB's ability to handle recursive functions when executing
+   in reverse.  */
+
+/* The recursive foo call must be the first line of the recursive
+   function, to test that we're not stepping too much and skipping
+   multiple calls when we should skip only one.  */
+int
+foo (int x)
+{
+  if (x) return foo (x-1);
+  return 0;
+}
+
+int
+bar (int x)
+{
+  int r = foo (x);
+  return 2*r;
+}
+
+int
+main ()
+{
+  int i = bar (5);
+  int j = foo (5);
+  return 0;			/* END OF MAIN */
+}
diff --git a/gdb/testsuite/gdb.reverse/recursion.exp b/gdb/testsuite/gdb.reverse/recursion.exp
new file mode 100644
index 00000000000..3fead0e8c8d
--- /dev/null
+++ b/gdb/testsuite/gdb.reverse/recursion.exp
@@ -0,0 +1,45 @@
+# Copyright 2008-2023 Free Software Foundation, Inc.
+
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3 of the License, or
+# (at your option) any later version.
+#
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+# This file is part of the GDB testsuite.  It tests reverse stepping
+# out of recursive functions.
+
+require supports_reverse
+
+standard_testfile
+
+if { [prepare_for_testing "failed to prepare" $testfile $srcfile] } {
+    return -1
+}
+
+runto_main
+
+if [supports_process_record] {
+    # Activate process record/replay
+    gdb_test_no_output "record" "turn on process record"
+}
+
+set end_of_program [gdb_get_line_number "END OF MAIN" "$srcfile"]
+gdb_breakpoint $end_of_program
+gdb_continue_to_breakpoint ".*$srcfile/$end_of_program.*"
+
+## test if GDB can reverse over a recursive program
+gdb_test "reverse-next" ".*int j = foo.*" "Skipping recursion from outside"
+## setup and next over a recursion for inside a recursive call
+repeat_cmd_until "reverse-step" ".*" ".*foo .x=4.*"
+gdb_test "reverse-next" ".*return foo.*" "Skipping recursion from inside"
+gdb_test "reverse-next" ".*foo .x=5.*" "print frame when stepping out"
+gdb_test "reverse-next" ".*bar .x=5.*" "stepping into a different function"
+gdb_test "reverse-next" "main .. at .*" "stepping back to main"
