Recursion using Lisp

The last function you're going to create is going to take some recursion, where the true power of list processing using Lisp lies. Iteration is possible (looping through each item one by one), but unlike general languages like the Java language, recursion is by far the easiest way to process lists in Lisp. You'll know exactly what recursion is by the end of this section.

Begin by creating a recursive concat function.

                
1   (defun concat_recursive (args_list)
2     (if (equal (cdr args_list) nil)
3         (car args_list)
4         (concat2 (car args_list)
5                  (concat_recursive (cdr args_list)))))

Recursion can be a difficult concept to tackle, so lets walk through this one:

• Assume an arbitrary argument list is passed to the above function.
• If there is only one element in the list (the (cdr args_list) portion on line 2 returns nil), return the single element (the (car args_list) on line 3).
• If there is more than one element in the list (meaning the (cdr args_list) portion on line 2 did not return nil), return the result of concatenating (using concat2) the first element of the list (see line 4) and the result of recursively calling concat_recursive using the result of (cdr args_list) as parameters (see line 5).

When passing the following list as a parameter, '("ho" "wd" "y" " h" "o"), the following is a walk-through of the output:

• The first time line 2 is reached, the if statement is false, and concat2 is called with "ho" and (concat_recursive '("wd" "y" " h" "o")).
• The second time line 2 is reached, the if statement is again false, and concat2 is called with "wd" and (concat_recursive '("y" " h" "o")).
• The third time line 2 is reached, the if statement is again false, and concat2 is called with "y" and (concat_recursive '(" h" "o")).
• The fourth time line 2 is reached, the if statement is again false, and concat2 is called with " h" and (concat_recursive '("o")).
• The fifth time is the magical time when the recursion ends. This is because this time, the if statement on line 2 is now true, and "o" is simply returned. The recursion unwinds as follows:
  
  • Fourth time: " h" and "o" are concatenated and returned.
  • Third time: "y" and " ho" are concatenated and returned.
  • Second time: "wd" and "y ho" are concatenated and returned.
  • First time: "ho" and "wdy ho" are concatenated and returned as the final result.

And there you have it — "howdy ho" ultimately gets returned, as shown below:

COMMON-LISP-USER>
(my_new_lisp_project:concat_recursive '("ho" "wd" "y" " h" "o"))

"howdy ho"

You have added recursion to your Cusp development arsenal. Try out the debugger next.