Recursive Function (Page 1) ● SmileBASIC Source Forums

Register

# Recursive Function

• #1 ✎ 198 MZ952 Intermediate Programmer I can make programs, but I still have trouble here and there. Programming Strength Drawing I like to draw! Hobbies Reading I like to read books! Hobbies So I recently saw an example of a recursive Function, and now I'm trying to understand it. I've written this: ```DEF SUM(A[]) IF(LEN(A))THEN RETURN(SUM(A)+POP(A)) END``` The function returns a Type mismatch error, and I'm not quite understanding why. My current reasoning is that the function is (somehow) returning an array which I inevitably am trying to assign to a variable, but I don't see why that is. This is how the function appears in my head: ```DEF SUM(A[]) IF(LEN(A))THEN RETURN(POP(A)+POP(A)+POP(A). . .+POP(A)) END``` The function calls iterations of itself LEN(A) times and sequentially sums up each iteration with the previous, returning the end result. Why is this a type mismatch? Posted
• #2 ✎ 1660 12Me21 Head Admin Third Year My account is over 3 years old Website Syntax Highlighter Received for creating the code syntax highlighter on SBS Night Person I like the quiet night and sleep late. Express Yourself Well, for one thing, if LEN(A) is 0, you're not returning anything. Posted
• #3 ✎ 198 MZ952 Intermediate Programmer I can make programs, but I still have trouble here and there. Programming Strength Drawing I like to draw! Hobbies Reading I like to read books! Hobbies
Well, for one thing, if LEN(A) is 0, you're not returning anything.
Lol that fixed it entirely. It looks like on the last step of the function it attempted to return something untyped or null and the whole thing broke down from there. Can't believe that escaped me. I thought the logic was flawed somewhere. Thank you! Corrected function: ```DEF SUM(A[]) IF(LEN(A)>.)THEN RETURN(SUM(A)+POP(A)) COPY(A),(1)(A),.RETURN(A[.]) END```
Posted Edited by MZ952
• #6 ✎ 1660 12Me21 Head Admin Third Year My account is over 3 years old Website Syntax Highlighter Received for creating the code syntax highlighter on SBS Night Person I like the quiet night and sleep late. Express Yourself ``` [funmodule][04:16]g: Lumage "NEXT(.)" Next breast``` Posted
• #7 ✎ 91 Simeon Scholar Received for knowing a great deal about programming topics Achievements Amazing Page Hidden Achievements Drawing I like to draw! Hobbies Ok, so actually what's happening is you don't have a base case, the array will get smaller and smaller, but you have no way of returning the final result so you just don't return anything which gives an error. So this code will work ```DEF SUM(A[]) IF LEN(A)==1 THEN RETURN A[0] RETURN SUM(A)+POP(A) END``` The issue with this is this does not allow empty arrays (you could simply add another base case check) A different approach: ```DEF SUM(A[]) IF LEN(A) THEN RETURN SUM(A)+POP(A) RETURN 0 END ``` This does allow empty arrays, and is allot lot harder to prove and understand. That's because the base case is actually the second to last step (not the last): First step [1,2,3] Second step [1,2]+3 Third step [1]+5 Fourth step []+6 *FIFTH STEP* 0+6 Function returns 6. You need to convert every component into number format, that means converting an empty array to 0. Something that doesn't work is switching the return order ```'FROM' RETURN SUM(A)+POP(A) 'TO' RETURN POP(A)+SUM(A)``` And this proves that SmileBASIC evaluates expressions from the right to the left. I took a class last semester called Design and Analysis of Algorithms, and that class evaluates recursive functions by pulling out their inner loops until the pattern is visible, to calculate the exact complexity in big O notation. Posted
• #8 ✎ 91 Simeon Scholar Received for knowing a great deal about programming topics Achievements Amazing Page Hidden Achievements Drawing I like to draw! Hobbies Hey, if you haven't seen this already then you should, it's a pretty cool example of recursion ```DRAW 200,120,119 DEF DRAW X,Y,R IF R<2 THEN RETURN GCIRCLE X,Y,R R=R/2 DRAW X+R,Y,R DRAW X-R,Y,R END``` Posted
• #9 ✎ 125 amihart My favorite example of recursion is this: ```DEF EMOD(B,P,M) IF P == 0 THEN RETURN 1 IF P MOD 2 == 0 THEN VAR R = EMOD(B, P/2, M) RETURN (R*R) MOD M ENDIF RETURN ((B MOD M) * EMOD(B, P-1, M)) MOD M END``` It's for calculating exponents in modular arithmetic of the form B^P MOD M. It's useful because the size of the number you're dealing with never exceeds the sides of M. So if you're dealing with something like 4546464^6346356 mod 12, you can't evaluate "4546464^6346356" because it's too big. But you can still evaluate this problem simply by breaking it up into chunks using recursion, and the size you need at each step never exceeds 12. Posted Edited by amihart