#1✎ 199MZ952Intermediate ProgrammerI can make programs, but I still have trouble here and there. Programming StrengthDrawingI like to draw!HobbiesReadingI like to read books!HobbiesSo 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✎ 162812Me21Head AdminThird YearMy account is over 3 years oldWebsiteSyntax HighlighterReceived for creating the code syntax highlighter on SBSNight PersonI like the quiet night and sleep late.Express YourselfWell, for one thing, if LEN(A) is 0, you're not returning anything.
Posted
#3✎ 199MZ952Intermediate ProgrammerI can make programs, but I still have trouble here and there. Programming StrengthDrawingI like to draw!HobbiesReadingI 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
#5✎ 199MZ952Intermediate ProgrammerI can make programs, but I still have trouble here and there. Programming StrengthDrawingI like to draw!HobbiesReadingI like to read books!Hobbies
#6✎ 162812Me21Head AdminThird YearMy account is over 3 years oldWebsiteSyntax HighlighterReceived for creating the code syntax highlighter on SBSNight PersonI like the quiet night and sleep late.Express Yourself [funmodule][04:16]g: Lumage "NEXT(.)"
Next breast
Posted
#7✎ 91SimeonScholarReceived for knowing a great deal about programming topicsAchievementsAmazing PageHiddenAchievementsDrawingI like to draw!HobbiesOk, 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✎ 91SimeonScholarReceived for knowing a great deal about programming topicsAchievementsAmazing PageHiddenAchievementsDrawingI like to draw!HobbiesHey, 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✎ 125amihartMy 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