Abstract

Recursive algorithms involve functions calling themselves until a base case is reached. Tail Recursion (TR), where the recursive call is the final action, closely resembles iteration and tends to be more accessible for students. In contrast, Non-Tail Recursion (NTR) requires managing function states on the call stack, introducing greater cognitive complexity. Addressing questions in Threshold Concept (TC) theory, such as the nature of “troublesome knowledge” and the role of “liminal space” in learning, the study investigates how TR and NTR differ in their conceptual demand and whether they exhibit the troublesome characteristics of a TC in computer science education. Findings reveal that NTR strongly aligns with TC characteristics due to its abstract and challenging nature, while TR does not. By distinguishing which form of recursion embodies the troublesome and liminal traits of TC, the study advances TC research, showing that not all manifestations of a concept are equally troublesome. It provides empirical evidence for practitioners interested in designing effective pedagogies.

Keywords: troublesome knowledge, Computer Science education, recursion, tail recursion, non-tail recursion, liminal Space; iteration

Despite its central role in computer science curricula, recursion continues to present significant challenges for students. Its reliance on understanding call stacks (how function calls are stored and resumed), abstract control flow (the order in which execution moves across calls), and base cases (the condition that stops further calls), often pushes students to fall back on iterative approaches, even when recursion is the more natural solution. While prior studies have established recursion’s difficulty (Kiesler, 2022; Sanders & Scholtz, 2012), only limited work has explored how its different forms, particularly Tail Recursion (TR) and Non-tail recursion (NTR) vary in cognitive demand for novice learners. Recent research by Baron and Feitelson (2024) highlights that comprehension is especially hindered in NTR and that TR may be more accessible to learners than NTR, yet the evidence for this distinction in pre-university student populations remains sparse. Our study responds to that gap by comparing student performance and reasoning across TR, NTR, and their iterative equivalents. By linking these differences to threshold concept theory, the research seeks to clarify which forms of recursion may represent a true threshold for learners.

Literature Review

Ray Land (CELatElon, 2019) described threshold concept (TC) as one that allows computer science students who are stuck when learning a concept and their teachers who get stuck teaching it, to get out of the “stuck space.” This is also referred to as the liminal space – a transitional phase where learners are in an “in-between” state, struggle with new and challenging ideas before fully understanding them (Land et al, 2014; Irving et al., 2019). This phase is often marked by troublesomeness, where learners encounter concepts that are difficult to understand, counter-intuitive, or even alien to their previous understanding. Some studies suggest that recursion may meet the criteria of a TC (Boustedt et al., 2007).

This troublesome nature is a key aspect of TCs, as it is through navigating these challenging liminal spaces that learners achieve a deeper, transformative shift in understanding (Peter et al. 2014). When students are stuck in the liminal space, they may experience frustration and will usually take different paths to attain full understanding (Eckerdal et al., 2007) or as Meyer and Land (2003) puts it, the “rite of passage.”

Recursion often ranks among the most cognitively demanding programming concepts for computer science students (Fellah and Bandi, 2018; Nzemeke et al. 2024). It can be particularly challenging when significant computation occurs after the recursive call, as in NTR. While problems that naturally fit the TR form are generally easier for students to understand, forcing a transformation into TR can introduce additional cognitive load and sometimes obscure the algorithm’s underlying intent, making comprehension more difficult (Baron & Feitelson, 2024).

A common way to investigate novice students’ difficulties with recursion is to compare it with iteration, which is often viewed as more straightforward and intuitive (Endres et al., 2021). Benander et al. (1996), in an experiment testing whether recursion is indeed harder to understand, found a statistically significant difference in comprehension favouring recursion, though they called for further empirical research in this area. Mirolo (2012) similarly challenged the assumption, arguing that problem difficulty depends more on task characteristics than on the programming paradigm itself. Endres et al. (2021) add that problem framing strongly influences outcomes: students performed better on iterative versions of non-branching numerical tasks but excelled with recursion for array classification.

There are also suggestions that the sequencing of recursion and iteration instruction with regards to when they are taught, is closely related to how well students understand these concepts. Teaching iteration first is often justified for its broader applicability and lower cognitive demand (Kessler & Anderson, 1986; Wiedenbeck, 1989). Nzemeke et al. (2024) provide complementary insights from the viewpoint of teachers. They found that recursion is typically introduced to students after iteration, and most of the surveyed teachers perceived it as a more challenging concept for students. It may be argued that while teaching iteration (before recursion) help students understand the idea of repetition, it may unintentionally reinforce loop-based mental models that hinder comprehension of NTR. Turbak et al. (1999) report that teaching recursion before iteration improved mastery of both, and Maiorana et al. (2021) recommend introducing both early to promote direct comparison and deeper algorithmic understanding. Guzdial (2018) argues that these concerns remain relevant and should be revisited through modern replication studies.

Research Question

How do learners experience recursion as a potential Threshold Concept, and in what ways do Tail and Non-Tail recursion differ in the liminal struggles and pathways of conceptual progression?

Research Methods and Data Collection

Using a mixed-method approach, 41 students were surveyed to gather quantitative and qualitative data on their experiences learning recursion. The students targeted all study computer science in Key Stage 4 (students aged 14 to 15) and Key Stage 5 (students aged 16 to 18) in a secondary school and Sixth Form College in England, United Kingdom. They have learned core programming concepts including recursion, sequence, iteration, and selection, functional and procedural paradigms, along with techniques such as parameter passing, using arguments, and returning values. They also understand the purpose of algorithms and have been taught how to construct and trace them for a given task.

A random name selector software was used to put students into two groups (Group A and Group B). Random assignment of students to groups plays a crucial role in allowing statistical tests to fairly compare outcomes between different groups. It’s the most effective strategy for achieving such group equivalence, guarding against selection bias (Skelly et al., 2012).

Students in Group A traced TR and NTR algorithms, while those in Group B solved their equivalent iterative versions. These parallel tasks enabled comparison of conceptual understanding and problem‑solving strategies without bias. By pairing each recursive algorithm with an iterative counterpart performing the same core operations, the design isolated recursion as the variable of interest. This control ensured differences in performance reflected the nature of recursion rather than task complexity, enabling evaluation of whether recursion, relative to iteration, exhibits the troublesome characteristics of a TC. Quantitative measures (e.g., base‑case identification, output prediction, difficulty ratings) and qualitative evidence (e.g., justifications of responses) were designed to help reveal misconceptions and cognitive approaches.

Ethical approval from the City St George’s university’s ethics committee was obtained.

Analysing Key Questions Used

In addition to other survey questions, students in Group A were tasked with solving AlgorithmOneA (Fig. 1) and AlgorithmTwoA (Fig. 3), while those in Group B completed AlgorithmOneB (Fig. 2) and AlgorithmTwoB (Fig. 4).

AlgorithmOneA (NTR) approaches the problem recursively, decreasing n by 3 until n ≤ 1 and printing n x 4 after each call; AlgorithmOneB uses iteration, increasing i by 3 in a loop until i exceeds n, printing i x 4 each time. Despite the difference in their recursive versus their iterative structure, both share identical core logic including counter-adjustment by 3, multiplication by 4, and then print.

AlgorithmTwoA and AlgorithmTwoB both calculate the sum of integers from 1 to n while printing a countdown from n to 1, achieving the same result through tail recursion and iteration respectively.

Fig.1 AlgorithmOneA

Fig.2 AlgorithmOneB

Fig.3 AlgorithmTwoA

Fig 4 AlgorithmTwoB

One of the open-ended questions invited students who reported difficulties with recursion to describe the sources of their confusion and the strategies they used to overcome it, as discussed further in the qualitative findings section.

Importance of Collecting Mixed Data

Using both quantitative and qualitative data was essential because Threshold Concepts (TC) research requires evidence of performance outcomes as well as the lived experience of liminality (Meyer et al., 2010). The quantitative results identified where difficulties with TR, NTR, and iteration were most pronounced, while the qualitative reflections explained the misconceptions, mental models, and disorientation underlying those patterns. Together, they provided a fuller picture of how students navigated or became stuck within the conceptual transformation required to understand recursion.

Quantitative Findings

With 71% of students reporting difficulties, the findings support the view that recursion has troublesome characteristics of a TC. A chi-squared test comparing how students performed on Tail Recursion (TR), Non-Tail Recursion (NTR) and their equivalent iterative algorithm problems revealed NTR is significantly more difficult than its iterative equivalent (p = 0.0028), while no significant difference was observed between TR and its iterative equivalent algorithms (p = 0.275). Further analysis showed NTR is notably more challenging than TR (p = 0.0006), whereas iterative versions of both were found similarly accessible (p = 0.52).

These findings suggest that while TR’s similarity to iteration makes it more accessible once the base case is understood, NTR introduces another layer of difficulty due to its reliance on deferred computation and management of the call stack which disrupts students’ iterative mental models, causing a greater disjunction (Savin-Baden, 2008) and appears to leave many students stuck in the liminal space. This aligns with Baron and Feitelson (2024), who found experienced programmers also found TR easier to comprehend when it aligned naturally with the problem. Our study extends these findings to pre-university learners.

Qualitative Findings

The liminal nature of learning recursion was evident as students worked to reframe their thinking about program execution and function completion. Their reflections revealed the disorienting nature of this stage, where prior assumptions must be set aside before new understandings form. One student noted, “The basic understanding of recursion when I was first introduced to it was very confusing and so I had to watch videos on it at home to help me understand it clearly.” Others described recursion as “not very intuitive” and requiring “time to adapt from other programming methodologies such as iterative programming.”

Some students initially described recursion in iterative terms, treating it as a loop that would “keep going until the condition is false,” revealing reliance on pre-existing mental models. Others struggled to understand that each recursive call maintains its own scope and variables, particularly in Non-Tail Recursion (NTR), where additional computation occurs after the recursive call. As one reflected, “Prior to learning about parameter passing and stacks in depth, I was unaware of the different scopes of each function call and originally thought that the variables were overwritten…”

Base-case errors were common in both TR and NTR, especially in deciding when recursion should stop or how return values are handled. One student commented, “The difficulty in recursion for myself is understanding when the exit condition is met that stops the recursive process, and tracing back the return variables from each function called in the stack.” To compensate, some students relied on external scaffolds such as tracing diagrams or step-by-step notes, illustrating the cognitive load of internalising recursive thinking. As one explained, “You cannot trace the algorithm as easily in your head … it is often more difficult to understand what the function is doing until you use paper and trace it manually.” These patterns indicate learners being caught in a liminal space typical of a TC.

Students’ conceptual journeys revealed important contrasts. Iteration and TR appear to follow relatively direct paths, with most learners progressing smoothly. By contrast, NTR involved prolonged liminal struggles, with some learners remaining unable to reach an integrated understanding. These qualitative patterns highlight the greater cognitive demands of NTR and its higher risk of incomplete conceptual development.

Conclusion

This study distinguishes Tail Recursion (TR) from Non‑Tail Recursion (NTR), showing NTR to be significantly more challenging for pre‑university learners and cautioning against treating recursion as a uniform construct in Threshold Concept (TC) research. NTR exhibits the troublesome characteristics of a TC and may qualify as one, while TR may not be if iteration is not considered a TC. The findings also reveal evidence of liminality, with students oscillating between iterative and recursive thinking, making errors in base cases, function scope, and flow, and relying on diagrams and stepwise tracing as coping strategies.

Interestingly, the contrast between TR and NTR mirrors how programming languages implement them. Many compilers optimize TR by converting it into iteration, reducing computational demands (Kristensen et al., 2023). This optimization reflects students’ reports that TR felt accessible once the base case was understood, aligning with iterative mental models. In contrast, NTR cannot be reduced to iteration, as each call must preserve deferred computations on the stack. This technical distinction parallels students’ prolonged struggles with multiple active calls and return values, reinforcing the finding that NTR more strongly exemplifies the troublesome and transformative traits of a TC. These distinctions and liminal patterns offer practical guidance for designing more effective pedagogies to support mastery of recursion.

Limitations and Future Work

The study examined only Tail and Non-Tail Recursion through specific tasks, so the findings should not be overgeneralised. Further research into different recursive structures and contexts is needed. Future work could explore recursion as a set of threshold concepts, focusing on call stacks, abstract control flow, and base cases, to better understand how these elements contribute to persistent misunderstandings of Non-Tail Recursion.

References

Baron, A., & Feitelson, D. G. (2024). Why is recursion hard to comprehend? An experiment with experienced programmers in Python. ITiCSE 2024, 115–121. https://doi.org/10.1145/3649217.3653636

Benander, A. C., Benander, B. A., & Pu, H. (1996). Recursion vs. iteration: An empirical study of comprehension. Journal of Systems and Software 32, 73–82.

Boustedt, J., Eckerdal, A., McCartney, R., Moström, J., Ratcliffe, M., Sanders, K., & Zander, C. (2007). Threshold concepts in computer science: Do they exist and are they useful? SIGCSE ’07, 504–508. https://doi.org/10.1145/1227310.1227482

Center for Engaged Learning (2019). Ray Land vlog. https://youtu.be/J5H5ykavOak (accessed 5 July 2024).

Eckerdal, A., McCartney, R., Moström, J., Sanders, K., Thomas, L., & Zander, C. (2007). From limen to lumen: Computing students in liminal spaces. ICER ’07, 123–132.

Endres, M., Weimer, W., & Kamil, A. (2021). An Analysis of Iterative and Recursive Problem Performance. Proceedings of the 52nd ACM Technical Symposium on Computer Science Education.

Fellah, A., & Bandi, A. (2018). The essence of recursion: reduction, delegation, and visualization. J. Comput. Sci. Coll., 33(5), 115–123.

Guzdial, M. (2018). Exploring the question of teaching recursion or iterative control structures first. Computing Ed Research – Guzdial’s Take. https://computinged.wordpress.com/2018/03/09/exploring-the-question-of-teaching-recursion-or-iterative-control-structures-first/ (accessed 22 Oct 2023).

Irving, G., Wright, A., & Hibbert, P. C. (2019). Threshold concept learning: Emotions and liminal space transitions. Management Learning (forthcoming).

Kessler, C. M., & Anderson, J. R. (1986). Learning flow of control: Recursive and iterative procedures. Human Computer Interaction,, 2(2), 135–166. https://doi.org/10.1207/s15327051hci0202_2

Kiesler, N. (2022). Mental models of recursion: A secondary analysis of novice learners’ steps and errors in Java exercises. PPIG 2022.

Kristensen, J. T., Kaarsgaard, R., & Thomsen, M. K. (2023). Tail recursion transformation for invertible functions. Reversible Computation 2023, 3–18. Springer. https://doi.org/10.1007/978-3-031-37775-4_1

Land, R., Rattray, J., & Vivian, P. (2014). Learning in the liminal space: A semiotic approach to threshold concepts. Higher Education, 67(2), 199–217. http://www.jstor.org/stable/43648647

Maiorana, F., Csizmadia, A., Richards, G., & Riedesel, C. (2021). Recursion versus iteration: A comparative approach for algorithm comprehension. In Auer, M. E., & Centea, D. (Eds.), Visions and Concepts for Education 4.0 (pp. 3–18). Springer. https://doi.org/10.1007/978-3-030-67209-6_27

Meyer, J. H. F., & Land, R. (2003). Threshold concepts and troublesome knowledge: Linkages to ways of thinking and practising. In ISL10 Improving Student Learning (pp. 412–424). Oxford Brookes University.

Meyer, Jan & Land, Ray & Baillie, Caroline. (2010). Threshold Concepts and Transformational Learning. 10.1163/9789460912078.

Mirolo, C. (2012). Is iteration really easier to learn than recursion for CS1 students? ICER ‘12, 99–104. https://doi.org/10.1145/2361276.2361296

Nzemeke, J., Begum, M., & Wood, J. (2024). Exploring teachers’ perspectives on navigating recursion pedagogies. PPIG 2024, 77–89. Liverpool University.

Peter, M., Harlow, A., Scott, J. B., McKie, D., Johnson, E. M., Moffat, K., & McKim, A. M. (2014). Threshold concepts: Impacts on teaching and learning at tertiary level. Commission Report for Teaching and Learning Research Initiative (pp. 1–21).

Sanders, I., & Scholtz, T. (2012). First year students’ understanding of flow of control in recursive algorithms. African Journal of Research in Mathematics, Science and Technology Education, 16(3), 348–362.

Savin-Baden, M. (2008). Learning spaces: Creating opportunities for knowledge creation in academic life. Maidenhead:SRHE/Open University Press.

Turbak, F., Royden, C., Stephan, J., & Herbst, J. (1999). Teaching recursion before loops in CS1. J. Comput. Small Coll., 14(4), 86–101.

Wiedenbeck, S. (1989). Learning iteration and recursion from examples. International Journal of Man-Machine Studies, Volume 30(1), 1–22. https://doi.org/10.1016/S0020-7373(89)80018-5